8种排序算法--快速排序
快速排序是非常优越的一种排序，时间复杂度为nlogn，空间复杂度为logn。
下面我说说他实现的排序的算法。
快速排序的实现思想：将一组数据，从里面随便找一个值为key值（一般以这组数的第一个数为key），然后用这个key值将数据划分为2部分（一边大于他的数，一边小于他的数）然后将这两边的数分别用这个方法来递归实现字。直到所有都排序完毕。
我们来看看这个数据如何进行快速排序的。
4 3 7 2 1 9 5 8 7
第1趟：key=4
2 3 1 4 7 9 5 8 7
第2趟：key=2
1 2 3 4 7 9 5 8 7
第3趟：key=9
1 2 3 4 7 5 7 8 9
第4趟：key=7
1 2 3 4 5 7 7 8 9
第5趟：完毕
1 2 3 4 5 7 7 8 9
我们可以看出来第一趟以4为key，一次排序完我们可以知道，比key小的在key的左边，比key大的在key 的右边。然后我们将两边的数分辨用相同的方法一直递归。当左边有序后，在去排右边。
还有一个疑问就是如何实现一趟排序的呢？
4 3 7 2 1 9 5 8 7 当以4为key以后，从最左边（除了key自身）找比不小于他的数，从最右边找不大于他的数。
4 3 1 2 7 9 5 8 7 不大于他的数用紫色，不小于他的用红色。如果紫色在红色的左边说明一趟已经排完了。我们就把紫色数和key交换，我们就可以看到一趟排完后
2 3 1 4 7 9 5 8 7 比key小的数在左边，比key大的数在右边
下面是实现的代码：
packagecom.fish.sort;
public class FastSort {
public static void main(String[] args) {
int[] data =new int[] {4, 3, 7, 2, 1, 9, 5, 8, 7 };
fastSort(data, 0, data.length - 1);
}
//实现快速排序
public static void fastSort(int[] data, int start, int end) {
if (start >= end)
{
return ;}
// 以起始索引为分界点1
int key = data[start];
int i = start + 1;
int j = end;
while (true) {
print(data);
while (i <= end && data[i] < key) {
i++;
}
while (j > start && data[j] > key) {
j--;
}
if (i < j) {
swap(data, i, j);
} else {
break;
}
System.out.println("----------------------------------------");
}
// 交换 j和分界点的值
swap(data, start, j);
// 递归左边的数
fastSort(data, start, j - 1);
// 递归右边的数
fastSort(data, j + 1, end);
}
public static void swap(int[] data,int i, int j) {
if (i == j) {
return;
}
data[i] = data[i] + data[j];
data[j] = data[i] - data[j];
data[i] = data[i] - data[j];
}
public static void print(int[] data) {
for (int i = 0; i < data.length; i++) {
System.out.print(data[i] +"\t");
}
System.out.println();
}
}
结果：
4 3 7 2 1 9 5 8 7 第一趟
----------------------------
4 3 1 2 7 9 5 8 7 第二趟
2 3 1 4 7 9 5 8 7
----------------------------
2 1 3 4 7 9 5 8 7 第三趟
1 2 3 4 7 9 5 8 7
----------------------------
1 2 3 4 7 7 5 8 9 第四趟
----------------------------
1 2 3 4 7 5 7 8 9 第五趟
1 2 3 4 7 5 7 8 9
1 2 3 4 5 7 7 8 9
虚线代表是同一趟的。