oynix

于无声处听惊雷,于无色处见繁花

快速排序

直白的说,快速排序的主要思想是分治,将一个大数组,分成两个数组,然后对两个数组分别排序。对小数组排序的时候,同样按照这种思想,分成两个,再排序。直到不能再分,也就是长度为1,那么这个小数组就排好,当所有的小数组都排好了的时候,整个大数组也就排好了。

既然要分成两部分,那么就要选定一个基准,快速排序里面管这个叫做pivot,左边的都比pivot小,右边的都比pivot大。选取pivot的方式有多种,选最左侧的、选最右侧的、或者随机选一个位置当pivot。

一般选最左侧位置的就好。然后,就需要将剩下的数字分成两部分。使用两个指针,一个指向最左侧位置,另一个指向最右侧位置。左侧指针向右移动,右侧指针向左移动。

在左指针向右扫的过程中,如果遇到比pivot大的数字,就停下来;同样,当右指针向左扫的过程中,如果遇到比pivot小的数字,也停下来,此时将两个指针的数字交换,然后又可以继续扫,直到相遇。

左侧指针走过的数字,都比pivot小,右侧指针走做的数字,都比pivot大,两个指针相遇则停止,这个时候以相遇位置为分界线,数组就分成了两部分,将pivot和相遇点交换即可。

然后将左侧是数组和右侧的数组分别重复这个过程,等到都完成时,也就排序完成了。

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
public class Solution
{
public int[] SortArray(int[] nums)
{
return QuickSort(nums, 0, nums.Length - 1);
}

private int[] QuickSort(int[] nums, int left, int right)
{
if (left >= right) return nums;

int l = left;

int r = right;

int pivot = nums[l];

while (left < right)
{
while (nums[right] > pivot && right > left)
{
right -= 1;
}

while (nums[left] <= pivot && left < right)
{
left += 1;
}

if (left != right)
{
(nums[left], nums[right]) = (nums[right], nums[left]);
}
}

if (l != left)
{
(nums[l], nums[left]) = (nums[left], nums[l]);
}

QuickSort(nums, l, left - 1);

QuickSort(nums, left + 1, r);

return nums;
}
}
------------- (完) -------------
  • 本文作者: oynix
  • 本文链接: https://oynix.com/2024/02/389a65957e41/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!

欢迎关注我的其它发布渠道