实例039 使用快速排序法对数组排序

发表于 分类于 ， Waline： 本文字数： 7.7k 阅读时长 ≈ 7 分钟

实例039 使用快速排序法对数组排序

实例说明

快速排序(QuickSort)是对气泡排序的一种改进,其排序速度相对较快。本实例演示如何使用快速排序法对一维数组进行排序,运行本实例,首先单击“生成随机数组”按钮,生成一个随机数组,并显示在上方的文本框中;然后单击“排序”按钮,使用快速排序法对生成的一维数组进行排序,并将排序后的一维数组显示在下方的文本框中。实例的运行效果如图511所示

实现过程

(3)编写“排序”按钮的事件处理方法,在该方法中利用快速排序算法对生成的随机数组进行排序,并将排序过程输出到文本域控件中。关键代码如下:

(4)编写快速排序方法quickSort,这个方法将被按钮的事件处理方法调用,该方法在实现快速排序的同时,把排序过程显示到文本域控件中。关键代码如下:

(5)由于快速排序方法中频繁地交换数组元素,而且在程序代码中出现的次数较多,所以应该把数组元素交换单独提炼为一个swap()方法,以实现代码重用,并且可以在该方法中掌握排序过程并显示到文本域控件。关键代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
private void quickSort(int[] array)
{
    quickSort(array, 0, array.length - 1);
}
private void quickSort(int[] array, int left, int right)
{
    if (left < right)
    {
        int splitIndex = divide(array, left, right);
        quickSort(array, left, splitIndex - 1);
        quickSort(array, splitIndex + 1, right);
    }
}
private int divide(int[] array, int left, int right)
{
    int splitPoint = array[left];
    int i = left;
    int j = right;
    while (i < j)
    {
        // 从右到左 找出比分割点小的元素
        while (j > i)
        {
            // 如果在右边找到比分割点小的数,结束查找
            if (array[j] < splitPoint)
            {
                break;
            }
            j--;
        }
        // 从左往右 找出比分割点大的元素
        while (i < j)
        {
            // 如果找到一个比分割点大的数,则结束查找
            if (array[i] > splitPoint)
            {
                break;
            }
            i++;
        }
        // j>i时交换j==i时不交换
        if (j > i)
        {
            swap(array, i, j);
            printSwap(array, i, j, left, right);;
        }
    }
    swap(array, left, i);
    printSwap(array, left, i, left, right);
    return i;
}
private void swap(int[] array, int i, int j)
{
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

技术要点

本实例主要用到了快速排序算法,下面对快速排序算法的实现原理进行详细讲解。快速排序算法是对冒泡排序算法的一种改进,它的基本思想是:
通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据小,然后再按此方法对这两部分数据分别进行快速排序。整个排序过程可以递归进行,以此使整个数据变成有序序列。
假设要排序的数组是A[1]...A[N],

  • 首先任意选取一个数据(通常选用第一个数据)作为关键数据,
  • 然后将所有比它小的数都放到它前面,
  • 所有比它大的数都放到它后面,

这个过程称为一趟快速排序,递归调用此过程,即可实现数组的快速排序。
使用快速排序法的排序过程如图5.12所示

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
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;
import java.awt.Font;

public class QuickSort2 extends JFrame
{
    private static final long serialVersionUID = -7934071799529975055L;
    private JPanel contentPane;

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

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

        JTextArea textAreaArray = new JTextArea();
        textAreaArray.setRows(1);
        GridBagConstraints gbc_arrayTextArea = new GridBagConstraints();
        gbc_arrayTextArea.insets = new Insets(0, 0, 5, 0);
        gbc_arrayTextArea.fill = GridBagConstraints.BOTH;
        gbc_arrayTextArea.gridx = 0;
        gbc_arrayTextArea.gridy = 0;
        contentPane.add(textAreaArray, gbc_arrayTextArea);

        JButton jButtonRandomArray = new JButton("生成随机数组");
        jButtonRandomArray.addActionListener(new ActionListener() {
            public void actionPerformed(ActionEvent e)
            {
                textAreaArray.setText("");
                int arrayLength = 10;
                int[] array = new int[arrayLength];
                Random random = new Random();
                for (int i = 0; i < array.length; i++)
                {
                    array[i] = random.nextInt(50);
                    textAreaArray.append("" + array[i]);
                    if (i < array.length - 1)
                    {
                        textAreaArray.append(",");
                    }
                }

            }
        });
        GridBagConstraints gbc_jButtonRandomArray = new GridBagConstraints();
        gbc_jButtonRandomArray.insets = new Insets(0, 0, 5, 0);
        gbc_jButtonRandomArray.gridx = 0;
        gbc_jButtonRandomArray.gridy = 1;
        contentPane.add(jButtonRandomArray, gbc_jButtonRandomArray);

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

        JTextArea textAreaShow = new JTextArea();
        textAreaShow.setFont(new Font("Monospaced", Font.PLAIN, 14));
        scrollPane.setViewportView(textAreaShow);

        JButton jButtonQuickSort = new JButton("快速排序");
        jButtonQuickSort.addActionListener(new ActionListener() {
            public void actionPerformed(ActionEvent e)
            {
                textAreaShow.setText("");
                String[] arrayStrs = textAreaArray.getText().split(",");
                int[] array = new int[arrayStrs.length];
                for (int i = 0; i < array.length; i++)
                {
                    array[i] = Integer.parseInt(arrayStrs[i]);
                }
                textAreaShow.append("排序之前:\n");
                printArray(array, textAreaShow);
                textAreaShow.append("\n");
                quickSort(array);
                textAreaShow.append("\n");
                textAreaShow.append("排序之后:\n");
                printArray(array, textAreaShow);
            }
            private void printArray(int[] array, JTextArea textAreaShow)
            {
                // textAreaShow.append("[");
                for (int i = 0; i < array.length; i++)
                {
                    textAreaShow.append("" + array[i]);
                    if (i < array.length - 1)
                    {
                        textAreaShow.append(",");
                    }
                }
                // textAreaShow.append("]");
                textAreaShow.append("\n");
            }
            private void quickSort(int[] array)
            {
                quickSort(array, 0, array.length - 1);
            }
            private void quickSort(int[] array, int left, int right)
            {
                if (left < right)
                {
                    int splitIndex = divide(array, left, right);
                    quickSort(array, left, splitIndex - 1);
                    quickSort(array, splitIndex + 1, right);
                }
            }
            private int divide(int[] array, int left, int right)
            {
                int splitPoint = array[left];
                int i = left;
                int j = right;
                while (i < j)
                {
                    // 从右到左 找出比分割点小的元素
                    while (j > i)
                    {
                        // 如果在右边找到比分割点小的数,结束查找
                        if (array[j] < splitPoint)
                        {
                            break;
                        }
                        j--;
                    }
                    // 从左往右 找出比分割点大的元素
                    while (i < j)
                    {
                        // 找到一个比分割点大的数,则结束查找
                        if (array[i] > splitPoint)
                        {
                            break;
                        }
                        i++;
                    }
                    if (j > i)
                    {
                        swap(array, i, j);
                        printSwap(array, i, j, left, right);;
                    }
                }
                swap(array, left, i);
                printSwap(array, left, i, left, right);
                // textAreaShow.append("分割点:" + array[i] + ",index=" + i+"\n");
                return i;
            }
            private void swap(int[] array, int i, int j)
            {
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
                // printSwap(array, i, j);
            }
            private void printSwap(int[] array, int i, int j, int left, int right)
            {
                for (int k = 0; k < array.length; k++)
                {
                    if (k == left)
                    {
                        textAreaShow.append("[");
                    }
                    if (k == i || k == j)
                    {
                        textAreaShow.append("'" + array[k] + "'");
                    } else
                    {
                        textAreaShow.append("" + array[k]);
                    }
                    if (k == right)
                    {
                        textAreaShow.append("]");
                    }
                    if (k < array.length - 1)
                        textAreaShow.append(",");
                }
                textAreaShow.append("\n");
            }
        });
        GridBagConstraints gbc_jButtonQuickSort = new GridBagConstraints();
        gbc_jButtonQuickSort.gridx = 0;
        gbc_jButtonQuickSort.gridy = 3;
        contentPane.add(jButtonQuickSort, gbc_jButtonQuickSort);
    }

}