快速排序递归与非递归

素颜马尾好姑娘i 2022-09-18 01:59 242阅读 0赞

递归法

##     ##

**快排的思想**

设当前需要排序的数组为int A\[bt...ed\]

分解：  
在A\[\]中任选一个记录作为基准（pivot），以pivot为基准将数组A划分为两个小的数组A\[bt...pivot-1\]和A\[pivot+1...ed\],并使左边的数组元素均小于等于pivot，右边数组元素均大于等于piovt。此时，pivot处于正确的位置上，它不需要再参加后续的排序

求解：  
递归的调用快速排序，对A\[bt...pivot-1\]和A\[pivot+1...ed\]进行快速排序

组合：  
跟归并排序不同，因为每次调用快速排序，左右两个数组均已有序，因此对于快速排序来说，组合是一个空操作

## 实现代码（C语言） ##

快排用c实现其实可以直接调用系统的qsort函数，自己写compare比较函数即可，在php里是调用usort函数，但是面试考察大部分都是不能调用系统函数的，所以这里提供一下代码，供参考：

**\[cpp\]**  [view plain][] [copy][view plain]

1.  /\*\* 
2.   \* 基准点排序 
3.   \* 
4.   \* T = O(n) 
5.   \* 
6.   \*/  
7.  **int** pivotLoc(**int** \*arr, **int** bt, **int** ed)  
8.  \{  
9.      **int** stand;  
10.   
11.     stand = arr\[bt\];  
12.   
13.     **while** (bt < ed) \{  
14.         **while** (bt < ed && arr\[ed\] >= stand)   ed --;  
15.         **if** (bt < ed) arr\[bt ++\] = arr\[ed\];  
16.   
17.         **while** (bt < ed && arr\[bt\] <= stand)   bt ++;  
18.         **if** (bt < ed) arr\[ed --\] = arr\[bt\];  
19.     \}  
20.   
21.     arr\[bt\] = stand;  
22.   
23.     **return** bt;  
24. \}  
25.   
26. /\*\* 
27.  \* 快排入口代码，递归策略 
28.  \* 
29.  \* T = O(nlogn) 
30.  \* 
31.  \*/  
32. **void** quickSort(**int** \*arr, **int** bt, **int** ed)  
33. \{  
34.     **int** pivot;  
35.   
36.     **if** (bt < ed) \{  
37.         pivot = pivotLoc(arr, bt, ed);  
38.         quickSort(arr, bt, pivot - 1);  
39.         quickSort(arr, pivot + 1, ed);  
40.     \}  
41. \}

### 优化 ###

快排的平均时间复杂度是O(nlogn),但是考虑一下最坏的情况：

假设给定的排序序列是逆序，例如5、4、3、2、1,然后用上述快排代码进行从小到大排序，很明显，快排从O（nlogn）降到了O(n^2)，如何避免这种情况呢？

解答：基准点的随机选取，我这里每次采用mid作为基准点

**\[cpp\]**  [view plain][] [copy][view plain]

1.  /\*\* 
2.   \* 快排优化，随机选取基准点 
3.   \* 
4.   \*/  
5.  **void** optimizeSort(**int** \*arr, **int** bt, **int** ed)  
6.  \{  
7.      **int** mid = bt + ((ed - bt) >> 1);  
8.    
9.      // 不使用额外空间，进行两数互换  
10.     **if** (arr\[bt\] != arr\[mid\]) \{  
11.         arr\[bt\] = arr\[bt\] ^ arr\[mid\];  
12.         arr\[mid\] = arr\[bt\] ^ arr\[mid\];  
13.         arr\[bt\] = arr\[bt\] ^ arr\[mid\];  
14.     \}  
15. \}  
16.   
17. /\*\* 
18.  \* 基准点排序 
19.  \* 
20.  \* T = O(n) 
21.  \* 
22.  \*/  
23. **int** pivotLoc(**int** \*arr, **int** bt, **int** ed)  
24. \{  
25.     **int** stand;  
26.       
27.     // 快排优化  
28.     **if** (bt < ed) \{  
29.         optimizeSort(arr, bt, ed);  
30.     \}  
31.   
32.     stand = arr\[bt\];  
33.   
34.     **while** (bt < ed) \{  
35.         **while** (bt < ed && arr\[ed\] >= stand)   ed --;  
36.         **if** (bt < ed) arr\[bt ++\] = arr\[ed\];  
37.   
38.         **while** (bt < ed && arr\[bt\] <= stand)   bt ++;  
39.         **if** (bt < ed) arr\[ed --\] = arr\[bt\];  
40.     \}  
41.   
42.     arr\[bt\] = stand;  
43.   
44.     **return** bt;  
45. \}  
46.   
47. /\*\* 
48.  \* 快排入口代码，递归策略 
49.  \* 
50.  \* T = O(nlogn) 
51.  \* 
52.  \*/  
53. **void** quickSort(**int** \*arr, **int** bt, **int** ed)  
54. \{  
55.     **int** pivot;  
56.   
57.     **if** (bt < ed) \{  
58.         pivot = pivotLoc(arr, bt, ed);  
59.         quickSort(arr, bt, pivot - 1);  
60.         quickSort(arr, pivot + 1, ed);  
61.     \}  
62. \}

非递归法

/*
    *BLOG:http://blog.csdn.net/wdzxl198
    *AUTHOR:Atlas
    *EMAIL:wdzxl198@163.com
    */
    
    #include<iostream>
    #include<stack>
    
    using namespace std;
    
    int Partition(int array[],int lhs,int rhs)
    {
    	int x = array[rhs];
    	int i = lhs - 1;
    	
    	for(int j=lhs;j<=rhs-1;j++)
    	{
    		if(array[j] <= x)
    		{
    			++i;
    			std::swap(array[i],array[j]);
    		}
    	}
    	std::swap(array[i+1],array[rhs]);
    	return i+1;
    }
    
    void QuickSort(int *arr,int left,int right)
    {
        stack<int> st;
        if(left < right)
        {
            int mid = Partition(arr,left,right);
            if(left < mid-1)
    	{
                st.push(left);
                st.push(mid-1);
            }
            if(mid+1 < right)
    	{
                st.push(mid+1);
                st.push(right);
            }
            
            while(!st.empty())
    	{
                int q = st.top();
                st.pop();
                int p = st.top();
                st.pop();
                
                mid = Partition(arr,p,q);
                if(p < mid-1)
    	    {
                    st.push(p);
                    st.push(mid-1);
                }
                if(mid+1 < q)
    	    {
                    st.push(mid+1);
                    st.push(q);
                }       
            }
        }
        else
        	return;
    }
    
    int main()
    {
    	int a[10] ={3,7,6,4,0,2,9,8,1,5};  
    	
    	for(int i=0;i<10;i++)
    	   cout<<a[i]<<" ";
    	cout<<endl; 
    	cout<<"快速排序：";	
    	QuickSort(a,0,9);
    
    	
    	for(int i=0;i<10;i++)
    		cout<<a[i]<<" ";
    	
    	cout<<endl;
    	system("PAUSE");
    	return 0;
    }

[view plain]: http://blog.csdn.net/wzy_1988/article/details/8043168#