java - 数据结构 - 快速排序
- -网上找结果很多都是无法排序有重复数据的,因此查了查资料写个改良版
百度百科:
快速排序算法通过多次比较和交换来实现排序,其排序流程如下:
(1)首先设定一个分界值,通过该分界值将数组分成左右两部分。
(2)将大于或等于分界值的数据集中到数组右边,小于分界值的数据集中到数组的左边。此时,左边部分中各元素都小于或等于分界值,而右边部分中各元素都大于或等于分界值。
(3)然后,左边和右边的数据可以独立排序。对于左侧的数组数据,又可以取一个分界值,将该部分数据分成左右两部分,同样在左边放置较小值,右边放置较大值。右侧的数组数据也可以做类似处理。
(4)重复上述过程,可以看出,这是一个递归定义。通过递归将左侧部分排好序后,再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后,整个数组的排序也就完成了。
思路:
1. low和high作为指针,
2. 起始以数组最左边(low)的数据作为基准base(所以右移一格,从第二个数开始判断排序)
3. low 从左往右直到大于等于base,保证low左边的地方,数据都小于base
4. high从右往左直到小于base,保证high经过的地方,数据都大于等于base。
5. 如果high <= low, 说明两个指针交叉了,也就是遍历完毕了。结束循环
6.如果high > low, 说明遍历没结束,交换low 和 high的数值
循环2,3,4,5,6直到触发5结束循环
7.循环结束后,high左边的数字全小于等于base,右边的全部大于base,high目前指向的数字是在目前的low左边或者和low一样,因此肯定小于base。
这时候交换base 和 high指向的数字。 这样就把base放在了中间位置,左边小于他,右边大于等于他。
8. 进行递归, 对base的左边和右边重复1-7的步骤,直到所有部分排序完毕。
package sort; public class Sort { public static void main(String[] args){ int[] a = new int[]{3,5,2,6,6,7,8,7,7,7,7,7,7,7,7,7,7,7,74,13,3,0,9,6,4,9,8}; //int[] a = new int[]{5, 4, 3, 2, 1}; Sort s = new Sort(); s.quickSort(a, 0, a.length - 1); showArray(a); } public int[] quickSort(int[] a, int start, int end){ if(start >= end) { //递归到达最底层 return a; } int base = start; int low = start + 1; int high = end; while(true){ while(low < end && a[low] < a[base]){ low++; } while(high > start && a[high] >= a[base]){ high--; } //找到位置看看是不是遍历完毕走过头了 if(high <= low){ break; } else{ //没走过头,交换high 和 low int i = a[low]; a[low] = a[high]; a[high] = i; } } //showArray(a); //此时high所在位置是一个< a[base]的数, 前面全小于a[base],后面全大于等于a[base] ,交换a[high]和a[base]把基准放在中间 int i = a[base]; a[base] = a[high]; a[high] = i; //递归 quickSort(a, start, high - 1 ); quickSort(a, high + 1, end); return a; } public static void showArray(int[] a){ for(int i:a) { System.out.print(i + " "); } System.out.println(); } }
相关推荐
LauraRan 2020-09-28
范范 2020-07-30
mingyunxiaohai 2020-07-28
mingyunxiaohai 2020-07-19
koushr 2020-11-12
zhangxiafll 2020-11-13
kikaylee 2020-10-31
范范 2020-10-28
MILemon 2020-10-22
hugebawu 2020-10-12
shenwenjie 2020-09-24
omyrobin 2020-09-23
guangcheng 2020-09-22
qiangde 2020-09-13
hanyujianke 2020-08-18
晨曦之星 2020-08-14
xiesheng 2020-08-06
KAIrving 2020-08-02