快速排序（超详细哦）

快速排序（超详细哦）"/>

快速排序（超详细哦）

一、快速排序基本思想

• 1.先从数列中取出一个数作为基准数
• 2.分区，将比基准数大的全放右边，小的数全放左边
• 3.再对左右区间重复第二步，直到各区间只有一个数

二、概括来说，就是

分治法+挖坑填数
分治法：大问题分解成各个小问题，对小问题求解，使得大问题得以解决

1.1挖坑填数

1.2分治法

挖坑填数后，基准数左边的数都比基准数小，右边的数都比它大。
这样子，我们再分别左边来一次挖坑填数，右边来一次挖坑填数，递归排序。

二、代码实现

void quickSort(int *arr, int l, int r)
{int start = l;int end = r;int temp = arr[start];if (start > end)return;while (start < end){//从右往左寻找比基准数小的元素while (start < end && arr[end] >= temp){end--;}//填坑if (start < end){arr[start] = arr[end];start++;}//从左往右寻找比基准数大的元素while (start < end && arr[start] <= temp){start++;}//填坑if (start < end){arr[end] = arr[start];end--;}//start与end相遇arr[start] = temp;quickSort(arr, l, start-1);quickSort(arr, start+1, r);}
}

三、代码测试

#include<iostream>
using namespace std;void printArray(int *arr, int len)
{for (int i = 0; i < len; i++){cout << arr[i] << " ";}cout << endl;
}int main(void)
{int array[] = {4, 2, 8, 0, 5, 7, 1, 9, 3};int len = sizeof(array) / sizeof(int);printArray(array, len);quickSort(array, 0, len-1);printArray(array, len);return 0;
}

四、结果