实例037 使用选择排序法对数组排序

实例说明
选择排序(SelectionSort)是一种简单直观的排序算法。本实例演示如何使用选择排序法.
对一维数组进行排序,运行本实例,

• 首先单击“生成随机数组”按钮,生成一个随机数组,并显示在上方的文本域控件中;
• 然后单击“排序”按钮,使用选择排序法对生成的维数组进行排序,并将排序后的一维数组显示在下方的文本域控件中。

实例的运行效果如图57所示。

实现过程

(3)编写“生成随机数组”按钮的事件处理方法,在该方法中创建Random随机数对象,初始化数组元素值时,通过该对象为每个数组元素生成随机数。关键代码如下:

JButton btnNewButton = new JButton("生成随机数");
btnNewButton.addActionListener(new ActionListener() {
    public void actionPerformed(ActionEvent e)
    {
        int[] numbers = new int[10];
        for (int i = 0; i < numbers.length; i++)
        {
            // 生成[0,50)之间的随机数
            numbers[i] = new Random().nextInt(50);
            if (i < numbers.length - 1)
                textArea.append(numbers[i] + " ");
            else
            {
                textArea.append(numbers[i] + "");
            }
        }
    }
});

(4)编写“排序”按钮的事件处理方法,在该方法中使用排序算法对生成的随机数组进行排序,然后把排序后的数组元素显示到文本域控件中。关键代码如下:

JButton btnNewButton_1 = new JButton("选择排序");
btnNewButton_1.addActionListener(new ActionListener() {
    public void actionPerformed(ActionEvent e)
    {
        // 清空显示区域
        textArea_1.setText("");
        // 解析字符串为int数组
        String numStr = textArea.getText();
        String[] numStrs = numStr.split(" ");
        int[] numbers = new int[numStrs.length];
        for (int i = 0; i < numbers.length; i++)
        {
            numbers[i] = Integer.parseInt(numStrs[i]);
        }
        // 排序
        for (int i = 0; i < numbers.length; i++)
        {
            int maxIndex = 0;
            // 查找未排序区域中的最大值
            for (int j = 0; j < numbers.length - i; j++)
            {
                if (numbers[j] > numbers[maxIndex])
                {
                    maxIndex = j;
                }
            }
            // 缓存最后的数
            int temp = numbers[numbers.length - 1 - i];
            // 将大的数换到最后
            numbers[numbers.length - 1 - i] = numbers[maxIndex];
            // 将最后的数换到
            numbers[maxIndex] = temp;
        }
        for (int i = 0; i < numbers.length; i++)
        {
            if (i < numbers.length - 1)
                textArea_1.append(numbers[i] + " ");
            else
            {
                textArea_1.append(numbers[i] + "");
            }
        }
    }
});

多学两招

利用选择排序法从数组中挑选最大值并放在数组最后,而遇到重复的相等值不会做任何处理,所以,如果程序允许数组有重复值的情况,建议使用选择排序方法,因为它的数据交换次数较少,相对速度也会略微提升,这取决于数组中重复值的数量

技术要点

本实例应用的主要技术点就是选择排序算法。选择排序算法的基本思想如下:
每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。

例如,对一个一维数组采用选择排序算法进行排序的过程如图5.8所示。

完整代码

package com;

import java.awt.EventQueue;
import java.awt.GridBagConstraints;
import java.awt.GridBagLayout;
import java.awt.Insets;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.util.Random;
import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.JScrollPane;
import javax.swing.JTextArea;
import javax.swing.border.EmptyBorder;

public class SelectSort extends JFrame
{

    private static final long serialVersionUID = -857370078330509549L;
    private JPanel contentPane;

    /**
     * Launch the application.
     */
    public static void main(String[] args)
    {
        EventQueue.invokeLater(new Runnable() {
            public void run()
            {
                try
                {
                    SelectSort frame = new SelectSort();
                    frame.setVisible(true);
                } catch (Exception e)
                {
                    e.printStackTrace();
                }
            }
        });
    }

    /**
     * Create the frame.
     */
    public SelectSort() {
        setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        setBounds(100, 100, 450, 300);
        contentPane = new JPanel();
        contentPane.setBorder(new EmptyBorder(5, 5, 5, 5));
        setContentPane(contentPane);
        GridBagLayout gbl_contentPane = new GridBagLayout();
        gbl_contentPane.rowHeights = new int[]{0, 0, 0, 0};
        gbl_contentPane.columnWeights = new double[]{1.0};
        gbl_contentPane.rowWeights = new double[]{1.0, 0.0, 1.0, 0.0};
        contentPane.setLayout(gbl_contentPane);

        JScrollPane scrollPane = new JScrollPane();
        GridBagConstraints gbc_scrollPane = new GridBagConstraints();
        gbc_scrollPane.fill = GridBagConstraints.BOTH;
        gbc_scrollPane.gridx = 0;
        gbc_scrollPane.gridy = 0;
        contentPane.add(scrollPane, gbc_scrollPane);

        JTextArea textArea = new JTextArea();
        scrollPane.setViewportView(textArea);

        JButton btnNewButton = new JButton("生成随机数");
        btnNewButton.addActionListener(new ActionListener() {
            public void actionPerformed(ActionEvent e)
            {
                textArea.setText("");
                int[] numbers = new int[10];
                for (int i = 0; i < numbers.length; i++)
                {
                    // 生成[0,50)之间的随机数
                    numbers[i] = new Random().nextInt(50);
                    if (i < numbers.length - 1)
                        textArea.append(numbers[i] + " ");
                    else
                    {
                        textArea.append(numbers[i] + "");
                    }
                }
            }
        });
        GridBagConstraints gbc_btnNewButton = new GridBagConstraints();
        gbc_btnNewButton.insets = new Insets(5, 0, 5, 0);
        gbc_btnNewButton.gridx = 0;
        gbc_btnNewButton.gridy = 1;
        contentPane.add(btnNewButton, gbc_btnNewButton);

        JScrollPane scrollPane_1 = new JScrollPane();
        GridBagConstraints gbc_scrollPane_1 = new GridBagConstraints();
        gbc_scrollPane_1.fill = GridBagConstraints.BOTH;
        gbc_scrollPane_1.gridx = 0;
        gbc_scrollPane_1.gridy = 2;
        contentPane.add(scrollPane_1, gbc_scrollPane_1);

        JTextArea textArea_1 = new JTextArea();
        textArea_1.setEditable(false);
        scrollPane_1.setViewportView(textArea_1);

        JButton btnNewButton_1 = new JButton("选择排序");
        btnNewButton_1.addActionListener(new ActionListener() {
            public void actionPerformed(ActionEvent e)
            {
                // 清空显示区域
                textArea_1.setText("");
                // 解析字符串为int数组
                String numStr = textArea.getText();
                String[] numStrs = numStr.split(" ");
                int[] numbers = new int[numStrs.length];
                for (int i = 0; i < numbers.length; i++)
                {
                    numbers[i] = Integer.parseInt(numStrs[i]);
                }
                // 选择排序法
                for (int i = 0; i < numbers.length; i++)
                {
                    int maxIndex = 0;
                    // 查找未排序区域中的最大值
                    for (int j = 0; j < numbers.length - i; j++)
                    {
                        if (numbers[j] > numbers[maxIndex])
                        {
                            maxIndex = j;
                        }
                    }
                    // 缓存最后的数
                    int temp = numbers[numbers.length - 1 - i];
                    // 将大的数换到最后
                    numbers[numbers.length - 1 - i] = numbers[maxIndex];
                    // 将最后的数换到
                    numbers[maxIndex] = temp;
                    // 打印排序结果
                    printEachSortingStepResults(numbers, i);
                }
                for (int i = 0; i < numbers.length; i++)
                {
                    if (i < numbers.length - 1)
                        textArea_1.append(numbers[i] + " ");
                    else
                    {
                        textArea_1.append(numbers[i] + "");
                    }
                }
            }
            /**
             * 打印每个排序步骤的结果
             * @param numbers 要排序的数组
             * @param i 选择排序算法运行的次数.
             */
            private void printEachSortingStepResults(int[] numbers, int i)
            {
                System.out.print("[");
                for (int j = 0; j < numbers.length; j++)
                {
                    System.out.print(numbers[j]);
                    if (j < numbers.length - 1 && j != numbers.length - i - 1)
                    {
                        System.out.print(",");
                    }
                    if (j == numbers.length - i - 1)
                    {
                        if (i == 0)
                            System.out.print("]");
                        else
                        {
                            System.out.print("],");
                        }
                    }

                }
                System.out.println("");
            }
        });
        GridBagConstraints gbc_btnNewButton_1 = new GridBagConstraints();
        gbc_btnNewButton_1.insets = new Insets(5, 0, 5, 0);
        gbc_btnNewButton_1.gridx = 0;
        gbc_btnNewButton_1.gridy = 3;
        contentPane.add(btnNewButton_1, gbc_btnNewButton_1);
        GridBagConstraints gbc_textArea = new GridBagConstraints();
        gbc_textArea.fill = GridBagConstraints.BOTH;
        gbc_textArea.gridx = 0;
        gbc_textArea.gridy = 1;
        GridBagConstraints gbc_textArea_1 = new GridBagConstraints();
        gbc_textArea_1.insets = new Insets(0, 0, 5, 0);
        gbc_textArea_1.fill = GridBagConstraints.BOTH;
        gbc_textArea_1.gridx = 0;
        gbc_textArea_1.gridy = 2;
    }

}

运行效果

生成的数组:

4 23 31 1 29 47 36 20 13 41

排序后的数组:

1 4 13 20 23 29 31 36 41 47

每一趟排序过程

[4,23,31,1,29,41,36,20,13,47]
[4,23,31,1,29,13,36,20,41],47
[4,23,31,1,29,13,20,36],41,47
[4,23,20,1,29,13,31],36,41,47
[4,23,20,1,13,29],31,36,41,47
[4,13,20,1,23],29,31,36,41,47
[4,13,1,20],23,29,31,36,41,47
[4,1,13],20,23,29,31,36,41,47
[1,4],13,20,23,29,31,36,41,47
[1],4,13,20,23,29,31,36,41,47