快速排序

快速排序是在面试中经常问到的算法题,也比较难掌握,特别是没有经常写算法的人儿。

算法思想

用笔者所理解的话来说,其算法思想是利用分而治之的思想,每一趟都保证左边比基准小,右边比基准大,而且递归划分排序。

一趟快速排序的算法是:

1、设置两个变量i、j,排序开始的时候:i=0,j=N-1;

2、以第一个数组元素作为基准数据,赋值给key,即key=A[0];

3、从j开始向前搜索,即由后开始向前搜索(j减1),找到第一个小于key的值A[j],将A[j]和A[i]互换;

4、从i开始向后搜索,即由前开始向后搜索(i++),找到第一个大于key的A[i],将A[i]和A[j]互换;

5、重复第3、4步,直到i=j;
(3,4步中,没找到符合条件的值,即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值,使得j=j-1,i=i+1,直至找到为止。找到符合条件的值,进行交换的时候i,
j指针位置不变。另外,i==j这一过程一定正好是i+或j-完成的时候,此时令循环结束)。

举个例子:

1、
对5,3,8,6,4这个无序序列进行快速排序,思路是右指针找比基准数小的,左指针找比基准数大的,然后交换之并更新基准位置。

2、5,3,8,6,4
用5作为比较的基准,right往左找,4<5,找到了4,left往右找,8>5,找到了8,然后交换,然后变成了5,3,4,6,8,同时新的基准位置修改为left,也就是4的位置,交换后变成4,
3, 5, 6, 8,而新的基准位置就是5的位置了

3、4,3,5,6,8 然后以5为基准划分成两个小组(4, 3)和(5, 6,
8),第一个小组和第二个小组分别进入到步骤1,最后形成(3,4)而(5,6,8)因为已经有序,所以整个过程就完成了。最终形成(3,4,5,6,8)

上面留下来了一个问题为什么一定要j指针先动呢?首先这也不是绝对的,这取决于基准数的位置,因为在最后两个指针相遇的时候,要交换基准数到相遇的位置。一般选取第一个数作为基准数,那么就是在左边,所以最后相遇的数要和基准数交换,那么相遇的数一定要比基准数小。所以j指针先移动才能先找到比基准数小的数。

时间复杂度

快速排序是不稳定的,其时间平均时间复杂度是O ( nlgn )。

伪代码

void quickSort(int a[], int len, int left, int right) {

// 所有都排序完毕了,就退出递归

if left >= right {

return;

}

// 每一趟划分,使左边的比基准小,右边的比基准大,并返回新的基准的位置

int baseIndex = partition(a, len, left, right);

// 递归排序左部分

quickSort(a, len, left, baseIndex - 1);

// 递归排序右部分

quickSort(a, len, baseIndex + 1, right)

}

int partition(int a[], int len, int left, int right) {

// 记录哪个是基准数

int base = a[left];

// 记录当前基准数的位置

int baseIndex = left;

while left < right {

// 先从右边往左边扫描,找到第一个比base还要小的数,但是不能与left相遇

while left < right && a[right] >= base {

right–;

}

// 再从左边往右边扫描,找到第一个比base还要大的数,但是不能与right相遇

while left < right && a[left] <= base {

left++;

}

// 将所扫描到的第一个比基准数小和第一个比基准数大的数交换

swap(a, left, right);

}

// 交换left与baseIndex对应的元素,将left位置的元素作为新的基准数

swap(a, baseIndex, left);

// 返回新的基准位置

return left;

}

void swap(int a[], int i, int j) {

int temp = a[i];

a[i] = a[j];

a[j] = temp;

}

C语言版

void quickSort(int a[], int len, int left, int right) {

if (left >= right) {

return;

}

// 一次划分后,得到基准数据的位置

int baseIndex = partition(a, len, left, right);

// 快排左边部分

quickSort(a, len, left, baseIndex - 1);

// 快排右边部分

quickSort(a, len, baseIndex + 1, right);

}

int partition(int a[], int len, int left, int right) {

// 每一次的划分,都让第一个元素作为基准

int base = a[left];

// 记下刚开始的基准的位置, 便于最后相遇时交换

int baseIndex = left;

while (left < right) {

// 查找右部分比base还小的元素的下标

while (left < right && a[right] >= base) {

right–;

}

// 查找左部分比base还大的元素的下标

while (left < right && a[left] <= base) {

left++;

}

// 将这一趟比基准大和比基准小的所找到的第一个值,互相交换

swap(a, left, right);

}

// 在left与right相遇时,将基准数与相遇点交换

// 这样这一次划分,就可以保证左边的比基准数小,右边的比基准数大

swap(a, baseIndex, left);

// 划分完成后,以left位置的元素作为新的基准,分成左右序列,分别递归排序

return left;

}

void swap(int a[], int i, int j) {

int temp = a[i];

a[i] = a[j];

a[j] = temp;

}

Swift版

func quickSort(inout a: [Int], left: Int, right: Int) {

if left >= right {

return

}

let baseIndex = partition(&a, left: left, right: right)

quickSort(&a, left: left, right: baseIndex - 1)

quickSort(&a, left: baseIndex + 1, right: right)

}

func partition(inout a: [Int], var left: Int, var right: Int) ->Int {

let base = a[left]

let baseIndex = left

while left < right {

while left < right && a[right] >= base {

right–

}

while left < right && a[left] <= base {

left++

}

swapInt(&a, i: left, j: right)

}

swapInt(&a, i: baseIndex, j: left)

return left

}

func swapInt(inout a: [Int], i: Int, j: Int) {

let temp = a[i]

a[i] = a[j]

a[j] = temp

}

0%