各个版本的快速排序源码

编程
目录

废话不多说，直接附上源码：

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;
//头尾元素比较的快排一趟排序算法
template <class T>
int partition(T *array, int begin, int end )
{
    T index_value = array[begin];
    
    int i = begin;
    int j = end + 1;
    while(1)
    {
        for(++i;i < j; ++i)
        {
            if(array[i] > index_value)
                break;
        }
        for(--j;j > i; --j)
        {
            if(array[j] < index_value)
                break;
        }
        if(j > i)
            swap(array[i], array[j]);
        else
            break;
    }
    swap(array[begin], array[j]);
    return j;
}
//头尾元素比较的快排一趟排序算法,partition的另一种写法
template <class T>
int partition2(T *array, int begin, int end )
{
    T index_value = array[begin];
    
    int i = begin;
    int j = end;
    while(i < j)
    {
        while(i < j && array[j] >= index_value) //从右边找到比比较值小的
            --j;
        if(i < j)
            array[i++] = array[j]; //将j 位的值换到前面的位置
        while(i < j && array[i] < index_value) //从左边找到比比较值大的
            ++i;
        if(i < j)
            array[j--] = array[i]; 
    }
    array[i] = index_value;
    return i;
}
//从前往后元素比较的快排一趟排序算法
template <class T>
int partition1(T * array, int begin, int end)
{
    T index_value = array[end];
    int i = begin - 1;
    int j = begin;
    for(;j < end; ++j)
    {
        if(array[j] < index_value)
        {
            ++i;
            if(i != j)
            {
                swap(array[j], array[i]);
            }
        }
    }
    swap(array[end], array[i + 1]);
    return i + 1;
}
//递归的快排版本
template <class T>
void quick_sort(T *array, int begin, int end)
{
    int pos = 0;
    if(begin < end)
    {
        //pos = partition1<int>(array, begin, end);
        pos = partition2<int>(array, begin, end);
    }
    else
        return ;
    quick_sort<T>(array, begin, pos - 1);
    quick_sort<T>(array, pos + 1, end);
}
//非递归的快排版本
template<class T>
void quick_sort_non_recursion(T *array, int begin, int end)
{
    stack<int> _stack;
    _stack.push(begin);
    _stack.push(end);
    for(;!_stack.empty();)
    {
        int _end = _stack.top();
        _stack.pop();
        int _begin = _stack.top(); 
        _stack.pop();
        int pos = 0;
        if(_begin < _end)
            pos = partition1<int>(array, _begin, _end);
            //pos = partition<int>(array, begin, end);
        else
            continue ;
        _stack.push(pos + 1);
        _stack.push(_end);
        _stack.push(_begin);
        _stack.push(pos - 1);
    }
}
int main()
{
    int array[10] = { 2 , 4, 1, 18, 5, 3, 23, 11, 5, 9};
    quick_sort<int>(array, 0, 9);
    //quick_sort_non_recursion<int>(array, 0, 9);
    int i = 0;
    for (;i < 10; ++i)
        cout << array[i] << "\t";
    cout << endl;
    return 0;
}

比较：
按效率上来讲，头尾比较的方法比从前往后比较的算法减少了元素交换的次数，效率稍微高些；但是头尾比较的算法是不稳定的排序算法，而从前往后的算法是稳定的排序算法，且从前往后遍历的方法也适合链表一类的数据结构，适用面更广泛。

迭代版本通过栈存放快排的区间，将递归方式转换成迭代。

本站总访问量次