快速排序

快速排序

测试代码，使用一个通用测试c++代码，代码如下

#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;
int main(){
    int val[10];
    srand((unsigned int)time(0));//随机数种子
    for(int i=0;i<10;i++) val[i]=(int)rand();//生成随机数
    for(int i=0;i<10;i++) cout<<val[i]<<" ";//输出初始数字
    cout<<endl;
    //这边调用排序方法
    for(int i=0;i<10;i++) cout<<val[i]<<" ";//输出排序后的数字
    cout<<endl;
    system("pause");
    return 0;
}

1.经典快速排序

伪代码

quick_sort(int* arr,int left,int right){
    if left>right 递归终止
    pivot = get_index(arr,left,right)
    quick_sort(arr,0,pivot-1)
    quick_sort(arr,pivot+1)
}
get_index(int* arr,int left,int right){
    tmp=arr[left]
    while left<right
        while left<right and arr[right]>=tmp
            right--
        arr[left]=arr[right]
        while left<right and arr[left]<=tmp
            left++
        arr[right]=arr[left]
    arr[left]=tmp
    return left
}

主要思想

1.找到pivot，进行左右递归，递归终止条件，左边数小于右边数

2.找到pivot方法，进行记住左边的数

​ 当右边数大于记住的数，右边指针左移

​ 右值赋值到左边

​ 当左边数小于记住的数，左边指针右移

​ 将左值移动到右边

​ 左值填充记住的数字

C语言代码实现

int get_index(int* arr,int left,int right){
    int tmp=arr[left];
    while(left<right){
        while(left<right&&arr[right]>=tmp) right--;
        arr[left]=arr[right];
        while(left<right&&arr[left]<=tmp) left++;
        arr[right]=arr[left];
    }
    arr[left]=tmp;
    return left;
}
void quick_sort(int* arr,int left,int right){
    if(left>right) return;
    int pivot=get_index(arr,left,right);
    //left是中介点
    quick_sort(arr,0,pivot-1);
    quick_sort(arr,pivot+1,right);
}