算法 - 快速排序
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了算法 - 快速排序，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含8164字，纯文字阅读大概需要12分钟。
内容图文
要点：分而治之，选取基准数，建立左右两个游标，两侧游标向基准数靠拢，交换元素，使左侧元素小于/大于基准数，右侧大于/小于基准数。并对左右部分进行递归。
1 import java.util.Random;
2
3 public class QuickSort<T extends Comparable> {
4
5 public void sort(T[] arr, int left, int right) {
6 if (left < right) {
7 int originLeft = left;
8 int originRight = right;
9 // 基准数
10 int index = new Random().nextInt(right - left) + left;
11 T base = arr[index];
12 System.out.println("基准数：" + base + "，区间：");
13 for (int i = 0; i < 11; i++) {
14 if (i >= left && i <= right) {
15 System.out.print("*");
16 continue;
17 }
18 System.out.print(" ");
19 }
20 System.out.println();
21 // 相等就不交换，否则会不稳定
22 if (arr[index] != arr[left]) {
23 arr[index] = arr[left];
24 arr[left] = base;
25 }
26 while (left < right) {
27 while (arr[right].compareTo(base) >= 0 && left < right) {
28 printArr(arr, " => 右标移动");
29 right--;
30 printSign(right, "右标 ←");
31 }
32 if (left < right) {
33 printArr(arr, " => 发生赋值");
34 printSign(left, "左标位置");
35 printSign(right, "右标位置");
36 arr[left] = arr[right];
37 printArr(arr, " => 右赋值给左");
38 left++;
39 printSign(left, "左标 →");
40 }
41 while (arr[left].compareTo(base) < 0 && left < right) {
42 printArr(arr, " => 左标移动");
43 left++;
44 printSign(left, "左标 →");
45 }
46 if (left < right) {
47 printArr(arr, " => 发生赋值");
48 printSign(left, "左标位置");
49 printSign(right, "右标位置");
50 arr[right] = arr[left];
51 printArr(arr, " => 左赋值给右");
52 right--;
53 printSign(right, "右标 ←");
54 }
55 }
56 arr[left] = base;
57 printArr(arr, " => 基准数交换");
58 System.out.println("- - - - - - - - - - - - - - - - - - - - ");
59 sort(arr, originLeft, left - 1);
60 sort(arr, left + 1, originRight);
61 }
62 }
63
64 private void printArr(T[] arr, String message) {
65 for (T n : arr) {
66 System.out.print(n);
67 }
68 System.out.print(message);
69 System.out.println();
70 }
71
72 private void printSign(int index, String message) {
73 String[] arr = new String[]{" ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " "};
74 arr[index] = "^";
75 for (String s : arr) {
76 System.out.print(s);
77 }
78 System.out.print(" => " + message);
79 System.out.println();
80 }
81
82 public static void main(String[] args) {
83 Integer[] arr = new Integer[]{1, 3, 8, 7, 6, 9, 5, 4, 3, 2, 0};
84 QuickSort as = new QuickSort();
85 as.sort(arr, 0, arr.length - 1);
86 }
87
88 /**
89 * 基准数：5，区间：
90 * ***********
91 * 53876914320 => 发生赋值
92 * ^ => 左标位置
93 * ^ => 右标位置
94 * 03876914320 => 右赋值给左
95 * ^ => 左标 →
96 * 03876914320 => 左标移动
97 * ^ => 左标 →
98 * 03876914320 => 发生赋值
99 * ^ => 左标位置
100 * ^ => 右标位置
101 * 03876914328 => 左赋值给右
102 * ^ => 右标 ←
103 * 03876914328 => 发生赋值
104 * ^ => 左标位置
105 * ^ => 右标位置
106 * 03276914328 => 右赋值给左
107 * ^ => 左标 →
108 * 03276914328 => 发生赋值
109 * ^ => 左标位置
110 * ^ => 右标位置
111 * 03276914378 => 左赋值给右
112 * ^ => 右标 ←
113 * 03276914378 => 发生赋值 => 顺序未改变，稳定
114 * ^ => 左标位置
115 * ^ => 右标位置
116 * 03236914378 => 右赋值给左
117 * ^ => 左标 →
118 * 03236914378 => 发生赋值
119 * ^ => 左标位置
120 * ^ => 右标位置
121 * 03236914678 => 左赋值给右
122 * ^ => 右标 ←
123 * 03236914678 => 发生赋值
124 * ^ => 左标位置
125 * ^ => 右标位置
126 * 03234914678 => 右赋值给左
127 * ^ => 左标 →
128 * 03234914678 => 发生赋值
129 * ^ => 左标位置
130 * ^ => 右标位置
131 * 03234919678 => 左赋值给右
132 * ^ => 右标 ←
133 * 03234919678 => 发生赋值
134 * ^ => 左标位置
135 * ^ => 右标位置
136 * 03234119678 => 右赋值给左
137 * ^ => 左标 →
138 * 03234159678 => 基准数交换
139 * - - - - - - - - - - - - - - - - - - - -
140 * 基准数：4，区间：
141 * ******
142 * 43230159678 => 发生赋值
143 * ^ => 左标位置
144 * ^ => 右标位置
145 * 13230159678 => 右赋值给左
146 * ^ => 左标 →
147 * 13230159678 => 左标移动
148 * ^ => 左标 →
149 * 13230159678 => 左标移动
150 * ^ => 左标 →
151 * 13230159678 => 左标移动
152 * ^ => 左标 →
153 * 13230159678 => 左标移动
154 * ^ => 左标 →
155 * 13230459678 => 基准数交换 => 顺序未改变，稳定
156 * - - - - - - - - - - - - - - - - - - - -
157 * 基准数：3，区间：
158 * *****
159 * 33210459678 => 发生赋值
160 * ^ => 左标位置
161 * ^ => 右标位置
162 * 03210459678 => 右赋值给左
163 * ^ => 左标 →
164 * 03210459678 => 发生赋值
165 * ^ => 左标位置
166 * ^ => 右标位置
167 * 03213459678 => 左赋值给右
168 * ^ => 右标 ←
169 * 03213459678 => 发生赋值
170 * ^ => 左标位置
171 * ^ => 右标位置
172 * 01213459678 => 右赋值给左
173 * ^ => 左标 →
174 * 01213459678 => 左标移动
175 * ^ => 左标 →
176 * 01233459678 => 基准数交换 => 顺序未改变，稳定
177 * - - - - - - - - - - - - - - - - - - - -
178 * 基准数：1，区间：
179 * ***
180 * 10233459678 => 右标移动
181 * ^ => 右标 ←
182 * 10233459678 => 发生赋值
183 * ^ => 左标位置
184 * ^ => 右标位置
185 * 00233459678 => 右赋值给左
186 * ^ => 左标 →
187 * 01233459678 => 基准数交换
188 * - - - - - - - - - - - - - - - - - - - -
189 * 基准数：9，区间：
190 * ****
191 * 01233459678 => 发生赋值
192 * ^ => 左标位置
193 * ^ => 右标位置
194 * 01233458678 => 右赋值给左
195 * ^ => 左标 →
196 * 01233458678 => 左标移动
197 * ^ => 左标 →
198 * 01233458678 => 左标移动
199 * ^ => 左标 →
200 * 01233458679 => 基准数交换
201 * - - - - - - - - - - - - - - - - - - - -
202 * 基准数：6，区间：
203 * ***
204 * 01233456879 => 右标移动
205 * ^ => 右标 ←
206 * 01233456879 => 右标移动
207 * ^ => 右标 ←
208 * 01233456879 => 基准数交换
209 * - - - - - - - - - - - - - - - - - - - -
210 * 基准数：8，区间：
211 * **
212 * 01233456879 => 发生赋值
213 * ^ => 左标位置
214 * ^ => 右标位置
215 * 01233456779 => 右赋值给左
216 * ^ => 左标 →
217 * 01233456789 => 基准数交换
218 * - - - - - - - - - - - - - - - - - - - -
219 *
220 * 分治法，递归
221 * => 遍历次数：与基准数选择和数据分布有关
222 * => 时间复杂度：O(nlogn)
223 * => 稳定性：稳定
224 *
225 */
226
227 }
内容总结
以上是互联网集市为您收集整理的算法 - 快速排序全部内容，希望文章能够帮你解决算法 - 快速排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】