8种排序算法快速排序
- 格式:doc
- 大小:34.50 KB
- 文档页数:3
快速排序是非常优越的一种排序,时间复杂度为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 89
第4趟:key=7
1 2 3 4 5 7 7 89
第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 279
5 8 7 不大于他的数用紫色,不小于他的用红色。如果紫色在红色的左边说明一趟已经排完了。我们就把紫色数和key交换,我们就可以看到一趟排完后2 3 1 4 7 9 5 8 7 比key小的数在左边,比key大的数在右边
下面是实现的代码:
package com.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
虚线代表是同一趟的。