vlambda博客
学习文章列表

快速排序递归代码课件在下文中。

排序(四)：快速排序

逻辑：本质是交换元素位置，跟冒泡似的，但是比冒泡的交换更加高效。

举例：4  1  2  8  5   从大到小排序

冒泡：一次冒泡结果 -> 4  2  8  5  1 ，期间交换了3次。

快速：以4为基准，两头交换，即左侧小于4的与右侧大于4的进行交换。所以一次快拍结果-> 4  5  8  2  1，期间交换了2次。然后基数归位 ->8  5  4  2  1， 期间交换1次，共交换3次。

        经过对比发现，快速排序经过3次交换就已经成序了，而一次冒泡排序经过四次交换还是无序的，还需要继续进行冒泡交换。可以看出，快速排序至少是比冒泡排序快的。

图解过程如下：

快速排序步骤：

      以数组中的某个值为基准，一般是首或者尾或者中间，咱们采用首元素为基准。

1、数组两端同时向中间遍历：本质就是两个下标变量，q,h，q++,h--。

2、交换：

从小到大排序：left遇到大于基数的停住，right遇到小于基数的停住，然后交换该两个元素。

        从大到小排序：left遇到小于基数的停住，right遇到大于基数的停住，然后交换该两个元素。

注意：如果以首元素为基数，则h先减，q后加

 如果以尾元素为基数，则h后减，q先加

 q==h  break，本轮交换结束。

3、基数归位：

 q==h相遇，并q跟基数不是同一个，则将该位置元素与基础元素交换

4、递归：

sort(arr, left, i-1);   //数据分段

sort(arr, j+1, right);

代码如下：

#include<stdio.h>

void Sort(int* arr, int left, int right)

{

if (left >= right)  //递归出口，结束条件

return;

else

{

int q = left, h = right;

while (q < h)  //两头找 交换

{

//h先--

while (q < h && arr[h] >= arr[left])

{

h--;

}

//q后++

while (q < h && arr[q] <= arr[left])

{

q++;

}

//相遇

if (q == h)

break;

//没相遇，就交换

int temp = arr[q];

arr[q] = arr[h];

arr[h] = temp;

}

// == 基数归位 

if (q != left)

{

int temp = arr[q];

arr[q] = arr[left];

arr[left] = temp;

}

//递归

Sort(arr, left, q - 1);

Sort(arr, h+ 1, right);

}

}

int main(void)

{

int arr[9] = {4,3,6,1,8,0,3,2,5};

Sort(arr, 0, 8);

return 0;

}