Java 快速排序两种实现

快速排序,只要学习过编程的人肯定都听说过这个名词,但是有时候写的时候还真蒙住了,网上搜罗了下以及查阅了"introduction to algorithm",暂时找到两种实现快排的方式,记录如下:

1.通过挖坑,分治的方式,需要左右交替遍历

思想如下:

Java 快速排序两种实现

代码实现:

     public static void quickSort1(int[] a, int s, int e) {
if (s >= e)
return;
int m = a[s];
int i = s, j = e;
while (i < j) {
while (a[j] > m && i < j)
j--;
if (i < j)
a[i++] = a[j];
while (a[i] < m && i < j)
i++;
if (i < j)
a[j--] = a[i];
}
a[i] = m;
quickSort1(a, s, i - 1);
quickSort1(a, i + 1, e);
}

2.将数组分为三个部分:小于中位数、大于中位数和未处理,是算法导论中提供的一种实现

思想如下:

Java 快速排序两种实现

代码如下:

     public static void quickSort2(int[] a, int s, int e) {
if (s >= e)
return;
int i = s - 1, j = s;
int m = a[e];
while (i <= j && i <= e && j <= e) {
if (a[j] <= m) {
int tmp = a[++i];
a[i] = a[j];
a[j++] = tmp;
}
else
++j;
}
quickSort2(a, s, i - 1);
quickSort2(a, i + 1, e);
}

快速排序的两种Java实现,以后发现有别的实现思路再补充。

上一篇:iOS开发:深入理解GCD 第二篇(dispatch_group、dispatch_barrier、基于线程安全的多读单写)


下一篇:python知识点总结