0%

快速排序

实现思路

以一值为基准,将比所有数划分为两部分,一部分比基准值大,一部分比基准值小。循环操作。

思路分析

  • 做一个递增排序
  • 开始时,以第一个元素为基准
  • 从后往前找比基准值小的值,并记录位置。
  • 从前往后找比基准值大的值,并记录位置。
  • 交换这两个值。
  • 重复上面操作,直到数组被分成两部分。
  • 然后把基准值跟比基准值小的部分的最后一个元素交换,此时,基准值找到自己位置。
  • 将比基准值小、比基准值大当成两个新数组,重复上面步骤。
  • 直至排序完成

代码实现

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
void Sort(int[] array, int low, int high) {
if (low >= high) return;
int j = partition(array, low, high);
Sort(array, low, j-1);
Sort(array, j+1, high);
}

int Partition(int[] array, int low, int high) {
int i = low;
int j = high + 1;
int value = array[low];
while (true) {
// 在左边找到比基准值大的
while (array[++i] < value) {
if (i == high) break;
}
// 在右边找到比基准值小的
while (array[--j] > value) {
if (j == low) break;
}

if (i >= j) break;

// 交换这两个值
Swap(array, i, j);
}
Swap(array, low, j)
return j;
}

完整代码

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
using System;

class QuickSort {

public static void Sort(int[] array) {
Sort(array, 0, array.Length-1);
}


public static void Sort(int[] array, int low, int high) {
if (low >= high) return;
int j = Partition(array, low, high);
Sort(array, low, j - 1);
Sort(array, j + 1, high);
}

private static int Partition(int[] array, int low, int high) {
int i = low;
int j = high + 1;
int value = array[low];
while (true) {
while (array[++i] < value) {
if (i == high) break;
}
while (array[--j] > value) {
if (j == low) break;
}

if (i >= j) break;
Swap(array, i, j);
}
Swap(array, low, j);
return j;
}

public static void Swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
public static void PrintArray(int[] array) {
foreach (int item in array) {
Console.Write("{0} ", item);
}
Console.WriteLine();
}

static void Main(string[] args) {
// 用于排序的数组
int[] array = { 25, 10, 100, 50, 5 };

Console.Write("排序前的数组:");
PrintArray(array);
Sort(array);
Console.Write("排序后的数组:");
PrintArray(array);

Console.ReadLine();
}
}