排序算法～快速排序

林不二 lv.1

发布时间：2022-11-25 12:05:41 117

相关标签： # 数据

    学习二分法查找的时候为了排序简单写了个冒泡排序，当数据量到达10W级的时候，效率真是低到没朋友了！
所以想实现个效率高些的排序，想到了快速排序！快速排序的思维是对半拆分，在一个数组中选取一个临界值，
如果小于这个临界值就将该数值前移，形成了初步排序的左右两边，之后递归左右两边即可！
    于是写了一个如下排序：
    private static void quickSort(int[] arr, int start, int end) {

if (start >= end) {
return;
}
int base = arr[start];
int in = start;
for (int i = start + 1; i < end; i++) {
if (arr[i] < base) {
int temp = arr[in];
arr[in] = arr[i];
arr[i] = temp;
in++;
}
}
quickSort(arr, start, in - 1);
quickSort(arr, in + 1, end);
}

试运行排序了一个小数组，发现成功了，不过多几个数值之后就发现了问题：

我取的第一个元素的值为标杆，排序过程中如果一直出现后面的数值小于标杆值，那么不会出现问题，

但是如果连续有几个数值大于标杆值，这几个值就会放在原位置不动，直到后面有小于标杆值的数值来替换。

这个问题想来可以通过交换‘标杆值’和‘第一次排完顺序的数组中的第一个大于标杆值的元素’的位置来解决，

但是这个标杆值在排序过程中被移动到哪里去了却无从所知。所以，还是修改代码吧！将标杆值最先一直留

在档次排序的第一位，排序结束之后，交换标杆值和最后一个小于标杆值的元素。于是优化为如下代码：

private static void quickSort(int[] arr, int start, int end) {
if (start >= end) {
return;
}
int base = arr[start];
int in = start; int temp; for (int i = start + 1; i < end; i++) {
if (arr[i] < base) {
in++;
temp = arr[in];
arr[in] = arr[i];
arr[i] = temp;
}
}
// 此处无需添加判断条件，直接运行即可，因为in处值一定小于首位置base
arr[start] = arr[in];
arr[in] = base;

quickSort(arr, start, in);
quickSort(arr, in + 1, end);
} 两个排序的比较数据： sort(arr); //冒泡 10000 - 300ms 100000 - 23s
quickSort(arr, 0, arr.length); // 10000 - 3ms // 100000 - 35ms

当数据量很大的时候，冒泡排序已经无法使用！注：建议自己按照排序算法的思维编写一下，慢慢优化就会发现最优写法！附上各种排序的复杂度分析，虽然有些我也没玩儿过！

文章来源： https://blog.51cto.com/u_12247864/5704099

特别声明：以上内容（图片及文字）均为互联网收集或者用户上传发布，本站仅提供信息存储服务！如有侵权或有涉及法律问题请联系我们。