快速排序C++实现（和随机快速排序）

约定不等于承诺〃 2022-05-24 01:39 206阅读 0赞

快速排序

思想：

存在一乱序数组A\[n\](0~n-1)，

第一步：

变量le和变量ri,分别保存首数组A\[0\]的下标（即le= 0;）

和尾数组A\[n-1\]的下标(即ri = n-1;)。

以A\[0\]为基数x = A\[le\],把变量le与变量ri分别赋给i,j(即i = le;j = ri)。

a.先从A\[j\]开始（包含A\[j\]）往 左 遍历，如果存在 比 x 值 小 的变量A\[j\]且i  < j ,则把A\[j\]的值赋给A\[i\] ,之后i右移一位(即i++)。

b.然后从A\[i\]开始(包含A\[i\])往 右 遍历，如果存在 比 x 值大的变量A\[i\], 且i  < j ,则把A\[i\]的值赋给A\[j\] ,之后j左移一位(即j--)。                                                        .

重复上面a,b(注意必须先a操作后b操作，因为选的以A\[1\]为基数)，直到i <j（即两边遍历相遇），则 A\[i\] = x（把基数放到分界处）。

第二步：

通过上面的排序可以得到以下标i为分界的数组，Aleft\[le~(i-1)\]和Aright\[(i+1)~ri\] 两个数组。

又把Aleft\[le~(i-1)\]和Aright\[(i+1)~ri\]两个数组分别重复第一步的a,b操作，最后得到排序好的数组（递归）。

时间复杂度：

![20180517214926353][]

算法实现:

#include<iostream>
    #include<malloc.h>
    #include <stdlib.h>
    
    using namespace std;
    	
    //快速排序  
    void quick_sort(int s[], int l, int r)  
    {  
        if (l < r)  
        {  
            //Swap(s[l], s[(l + r) / 2]); //将中间的这个数和第一个数交换 参见注1  
            int i = l, j = r;  
            while (i < j)  
            {  
    			/* int m = rand()%(r-l+ 1) + l;
    			 swap(s[m],s[l]);作为随机快速排序时，只需把随机到的数与s[l]交换 */
    	    x = s[l];
                while(i < j && s[j] >= x) // 从右向左找第一个小于x的数  
                    j--;    
                if(i < j)   
                    s[i++] = s[j];  
                  
                while(i < j && s[i] < x) // 从左向右找第一个大于等于x的数  
                    i++;    
                if(i < j)   
                    s[j--] = s[i];  
            }  
            s[i] = x;  
            quick_sort(s, l, i - 1); // 递归调用   
            quick_sort(s, i + 1, r);  
        }  
    }  
    int main(void)
    {
    	int *A;
    	int i;
    	
    	cin >> n;
    	if(n<0)
    		return 0;
    	A = (int *)malloc(sizeof(int)*n);
    	for(i=0;i<n;i++)
    	{
    		cin >> A[i];
    	}
    	
    	quick_sort(A,0,n-1);
    	
    	for(i=0;i<n;i++)
    	{
    		cout<< A[i] <<" ";
    	}
    	free(A);
    	
        return 0;
    }

在原作者文章下总结的,出处: [http://blog.csdn.net/morewindows/article/details/6684558][http_blog.csdn.net_morewindows_article_details_6684558]

[20180517214926353]: /images/20220524/712173ac736b4bb6bd4c125189a863f3.png
[http_blog.csdn.net_morewindows_article_details_6684558]: http://blog.csdn.net/morewindows/article/details/6684558