java算法系列之排序
手写快排
首先说一下什么是快排，比冒泡效率要高，快排的基本思路是首先找到一个基准元素，比如数组中最左边的那个位置，作为基准元素key，之后在最左边和最右边设立两个哨兵，i 和 j
之后，开始按住左哨兵(i)，让右哨兵(j)往左走(j--)，找到比key小的元素后，按住右哨兵(j),开始让左哨兵往右走(i++)，直到找到比key大的元素，让i和j脚下的值互换，此时完成第一趟快排，之后开始按照这个思路进行while循环，跳出循环的条件很简单，就是当两个哨兵碰头了，就跳出循环，此时，左边一块永远比key小，右边一块始终比key大！然后来个递归，对左右这两块进行一次快排，就o了。
package com.rsc.sort;
/**
* 人生中第一个快排
*
* @author
* @落雨 http://ae6623.cn
*/
public class QuickSort {
public static void quickSort(int[] a, int l, int r) {
int i = l;
int j = r;
if (l > r) {
return;
}
int key = a[l]; // 基准位key
while (i != j) {
// 先从右边的哨兵开始找
while (i < j && a[j] >= key) {
j--; // 直到找到了 a[j]<key的一个值，就停下来，得到了下标j
}
// 然后开始从左向右寻找
while (i < j && a[i] <= key) {
i++;
}
if (i < j) {
key = a[j];// 将key和a[j]交换
a[i] = a[j];// 将a[j]和a[i]互换，此时完成a[i]的赋值
a[j] = key;// 成功将a[j]和a[i]互换
}
}
// 现在将key归位
a[l] = a[i];
a[i] = key;
System.out.println("基准位:" + key);
// 递归处理左右两块
quickSort(a, l, i - 1); // 从左边开始一直到i-1，也就是基准位的前一位的排序
quickSort(a, i + 1, r); // 从i+1开始到最右边
for (int k : a) {
System.out.print(k + " ");
}
System.out.println();
}
public static void main(String[] args) {
int[] array = { 2, 1, 5, 4, 3, 7, 6 };
quickSort(array, 0, array.length - 1);
}
}
打印结果如下:
基准位:2
基准位:1
1 2 5 4 3 7 6
基准位:5
基准位:3
基准位:4
1 2 3 4 5 7 6
1 2 3 4 5 7 6
基准位:7
基准位:6
1 2 3 4 5 6 7
1 2 3 4 5 6 7
1 2 3 4 5 6 7
1 2 3 4 5 6 7