公告:欢迎访问,查看更多资源请点我^.^!            点我关闭广告
排序算法~快速排序
2018-09-11 11:19:53
1133人阅读
评论(0)
分类:算法
    学习二分法查找的时候为了排序简单写了个冒泡排序,当数据量到达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

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


分享一下:
赞一下(0)
博主资料
博主头像
zc521106
文章:34
浏览:19899
文章分类
Java(12)
NoSql(112)
数据库(12)
前端(12)
阅读排行
Java基础知识
(12)
NoSql应用
(112)
数据库Oracle语法
(12)
前端常用工具类
(12)
java web项目
(12)
linux安装mysql
(12)
评论区
这篇文章怎么样?写点评论吧!
姓名:
邮箱:
有回复时通知我:
发表
回复【10.20.30.32】:
暂无评论,快抢沙发!
* 以上用户言论只代表其个人观点,不代表iBlog网站的观点或立场,如有任何疑问请随时联系管理员...