当前位置: 首页 > 网站开发 > 正文

快速排序实现

1 星2 星3 星4 星5 星 (2 次投票, 评分: 5.00, 总分: 5)
Loading ... Loading ...
baidu_share

一、快速排序的基本思想
 设当前待排序的无序区为R[low..high],利用分治法可将快速排序的基本思想描述为:

①分解:
 在R[low..high]中任选一个记录作为基准(Pivot),以此基准将当前无序区划分为左、右两个较小的子区间R[low..pivotpos-1)和R[pivotpos+1..high],并使左边子区间中所有记录的关键字均小于等于基准记录(不妨记为pivot)的关键字pivot.key,右边的子区间中所有记录的关键字均大于等于pivot.key,而基准记录pivot则位于正确的位置(pivotpos)上,它无须参加后续的排序。

注意:
 划分的关键是要求出基准记录所在的位置pivotpos。划分的结果可以简单地表示为(注意pivot=R[pivotpos]):
 R[low..pivotpos-1].keys≤R[pivotpos].key≤R[pivotpos+1..high].keys
其中low≤pivotpos≤high。

②求解:
  通过递归调用快速排序对左、右子区间R[low..pivotpos-1]和R[pivotpos+1..high]快速排序。

完整的代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<iostream>  
#include<stack>  
using namespace std;   
 
int partition(int *arr , int low , int high)  
{  
    int pivo = arr[low];  
    while(low < high)  
    {  
        while(low < high && arr[high] >= pivo)  
            --high;  
        arr[low] = arr[high];  
        while(low < high && arr[low] <= pivo)  
            ++low;  
        arr[high] = arr[low];  
    }  
    arr[low] = pivo;  
    return low;  
}  
 
// 快速排序 递归  
void qsort(int *arr , int low , int high)  
{  
    if(low < high)  
    {  
        int pivo = partition(arr , low , high);  
        qsort(arr , low , pivo-1);  
        qsort(arr , pivo+1 , high);  
    }  
}  
 
// 快速排序 非递归  
void qsort_no_recursive(int *arr , int low , int high)  
{  
    stack<int>s;  
    int pivo;  
    if(low < high)  
    {  
        pivo = partition(arr , low , high);  
        if(low < pivo - 1)  
        {  
            s.push(low);  
            s.push(pivo-1);  
        }  
        if(pivo + 1 < high)  
        {  
            s.push(pivo+1);  
            s.push(high);  
        }  
        while(!s.empty())  
        {  
            high = s.top();  
            s.pop();  
            low = s.top();  
            s.pop();  
            pivo = partition(arr , low , high);  
            if(low < pivo - 1)  
            {  
                s.push(low);  
                s.push(pivo-1);  
            }  
            if(pivo + 1 < high)  
            {  
                s.push(pivo+1);  
                s.push(high);  
            }  
        }//while  
    }//if  
}  
 
//简单示例    
int main(void)    
{    
    int i , a[11] = {20,11,12,5,6,13,8,9,14,7,10};    
    printf("排序前的数据为:\n");    
    for(i = 0 ; i < 11 ; ++i)    
        printf("%d ",a[i]);    
    printf("\n");    
    //qsort(a , 0 , 10);  
    qsort_no_recursive(a , 0 , 10);  
    printf("排序后的数据为:\n");    
    for(i = 0 ; i < 11 ; ++i)   
        printf("%d ",a[i]);    
    printf("\n");  
    return 0;    
}

本文固定链接: http://www.chepoo.com/quick-sort.html | IT技术精华网

【上一篇】
【下一篇】

快速排序实现:等您坐沙发呢!

发表评论