快速排序

说明

快速排序(英语:Quicksort),又称划分交换排序(partition-exchange sort),一种排序算法,最早由东尼·霍尔提出。在平均状况下,排序n个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他Ο(n log n)算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来。

算法思路

1.选定一个合适的值(理想情况中值最好,但实现中一般使用数组第一个值),称为“枢轴”(pivot)。
2.重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
3.递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

//原地分区实现
private static int partition(int[] arr, int low, int high)
{
int pivot = arr[low];//以第一个值为pivot
while (low < high)
{
while (low < high && arr[high] >= pivot)
{
high--;
}
arr[low] = arr[high];
while (low < high && arr[low] <= pivot)
{
low++;
}
arr[high] = arr[low];
}
arr[low] = pivot;
return low;
}

private static void sort(int[] arr, int low, int high)
{
if (low >= high)
{
return;
}
int pivotIndex = partition(arr, low, high);
sort(arr, low, pivotIndex - 1);
sort(arr, pivotIndex + 1, high);
}

public static void main(String[] args)
{
int[] arr = {7, 4, 3, 8, 1, 2, 5, 6};

sort(arr, 0, arr.length - 1);
for (int i : arr)
{
System.out.println(i);
}
}
坚持原创技术分享,您的支持将鼓励我继续创作!
显示 Gitment 评论