快速排序

概述

快速排序是对冒泡排序的改进，空间复杂度在O(log2(n))和O(n)之间，时间复杂度在O(n*log2(n))和O(n^2^)之间。

原理

1.定义一个partition函数，该函数将low指针指向的数据元素找到并放置在其排序的最终位置，并将传入的数组以该元素为分界线，划分为大小两部分

2.在排序函数中，分别对数组的大小两部分进行递归

代码(C语言)

    #include "pch.h"  
    #include <iostream>  

    using namespace std;  

    int partition(int A[], int low,int high) {  
        //找到low位置对应元素在排序完成后的排序表中的位置，并将A数组以A[low]位界限划分成两部分，即大于A[low]和小于A[low]  
        int temp = A[low];  
        while (low < high) {  
            while (low < high&&A[high]>temp) high--;  
            A[low] = A[high];  
            while (low < high&&A[low] < temp) low++;  
            A[high] = A[low];  
        }  
        A[low] = temp;  
        return low;  
    }  

    void quick_sort(int A[], int low, int high) {  
        if (low < high) {  
            int pos = partition(A, low, high);  
            quick_sort(A, low, pos-1);  
            quick_sort(A, pos + 1, high);  
        }  

    }  

    int main()  
    {  
        int A[] = { 3,2,1,4 };//定义数组A  
        quick_sort(A,0,3);//对数组A排序  

        //循环输出A数组  
        int i;  
        for ( i = 0; i < 4; i++) {  
            cout << A[i] << endl;  
        }  

        system("pause");  
    }