Fork me on GitHub

排序算法实现

发表于 | 分类于
字数统计 1,823 | 阅读时长 10

前言

各种排序算法的实现，这东西，几天不写，就略感手生，需要定期不断温习，各种排序算法的思想都很清晰，写的过程中需要额外注意边界情况，递归结束条件，各种边界判断条件。没事写写，温故而知新。

手写排序算法

选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
//选择排序
struct Selection{
    static void select(int a[],int length){  //不稳定
        cout<<"select sort"<<endl;
        for(int i=0;i<length;++i){
            int mindex = i;
            for(int j=i;j<length;++j){
                if(a[j]<a[mindex]) mindex = j;
            }
            swap(a[i],a[mindex]);
        }
    }
};

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
//冒泡排序
struct Bubble{
    static void bubble(int a[],int length){  //稳定
        cout<<"bubble sort"<<endl;
        for(int i=0;i<length;++i){
            for(int j=0;j<length-i-1;++j){
                if(a[j]>a[j+1]) swap(a[j],a[j+1]);
            }
        }
    }
};

直接插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//插入排序
struct Insert{
    static void insert(int a[],int length){   //稳定
        cout<<"insert sort"<<endl;
        for(int i=1;i<length;++i){
            //找到带插入位置
            int tem = a[i];
            int j;
            for(j=i-1;j>=0;--j){
                if(a[j]>tem){
                    a[j+1] = a[j];
                }else break;
            }
            a[j+1] = tem;
        }
    }
};

希尔排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//希尔排序
struct Shell{
    static void shell(int a[],int length){   //不稳定
        cout<<"shell sort"<<endl;
        int h = 1;
        while(h<length/3) h = 3*h+1;   //增量分别为1,4,13,40,...
        while(h>=1){
            for(int i=h;i<length;++i){
                int tem = a[i];
                int j;
                for(j=i-h;j>=0;j-=h){
                    if(a[j]>tem){
                        a[j+h] = a[j];
                    }else break;
                }
                a[j+h] = tem;
            }
            h = h/3;
        }
    }
};

归并排序

  1. 递归版本

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    //递归归并排序
    struct MergeSort{   //稳定
        static void Merge_sort(int a[],int low,int high,int aux[]){  //将[low,high]进行归并
            if(high<=low) return;
            int mid = low + (high-low)/2;
            Merge_sort(a,low,mid,aux);
            Merge_sort(a,mid+1,high,aux);
            Merge(a,low,mid,high,aux);
        }
        static void Merge(int a[],int low,int mid,int high,int aux[]){   //将[low,mid] 与 [mid+1,high]进行归并
            int i = low;
            int j = mid + 1;
            int index = low;
            while(i<=mid&&j<=high){
                if(a[i]<a[j]) aux[index++] = a[i++];
                else aux[index++] = a[j++];
            }
            while(i<=mid) aux[index++] = a[i++];
            while(j<=high) aux[index++] = a[j++];
            for(int k=low;k<=high;++k){
                a[k] = aux[k];
            }
        }
    };

  2. 非递归版本

    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
    //非递归归并排序
    struct NoRecMergeSort{   //稳定
        static norecMergeSort(int a[],int length,int aux[]){
            cout<<"norecMergeSort"<<endl;
            for(int sz = 1;sz<length;sz=sz+sz){
                for(int lo = 0;lo<length-sz;lo+=sz+sz){     //lo = lo + sz + sz
                    Merge(a,lo,lo+sz-1,min(lo+sz+sz-1,length-1),aux);  // lo lo+sz-1  min(lo+sz+sz-1,length-1)
                }
            }
        }
        static void Merge(int a[],int low,int mid,int high,int aux[]){   //将[low,mid] 与 [mid+1,high]进行归并
            int i = low;
            int j = mid + 1;
            int index = low;
            while(i<=mid&&j<=high){
                if(a[i]<a[j]) aux[index++] = a[i++];
                else aux[index++] = a[j++];
            }
            while(i<=mid) aux[index++] = a[i++];
            while(j<=high) aux[index++] = a[j++];
            for(int k=low;k<=high;++k){
                a[k] = aux[k];
            }
        }
    };

快速排序

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
//快速排序
struct QuickSort{   //不稳定
    static void quicksort(int a[],int low,int high){    //对[low,high]进行快排
        if(high<=low) return;
        int j = Partition(a,low,high);
        quicksort(a,low,j-1);
        quicksort(a,j+1,high);
    }
    static int Partition(int a[],int low,int high){
        int i = low;
        int j = high + 1;
        int v = a[low];
        while(true){
            while(a[++i]<=v) {
                if(i==high) break;
            }
            while(a[--j]>=v) {
                if(j==low) break;
            }
            if(i>=j) break;
            swap(a[i],a[j]);
        }
        swap(a[low],a[j]);
        return j;
    }
};

堆排序

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
//堆排序
struct HeapSort{   //大根堆
    static void Sink(int a[],int length,int index){   //数组下标为index的元素进行下沉操作
        while(2*index+1<length){  //有左孩子节点
            int big = 2*index+1;
            if((2*index+2<length) && (a[2*index+2]>a[2*index+1])) { big = 2*index+2; }  //右子节点存在且大于左子节点
            if(a[big]<=a[index]) break;  //已经有序，无须交换
            swap(a[index],a[big]);  //父节点和左右子节点中的较大值进行交换
            index = big;
        }
    }
    static void heapSort(int a[],int length){
        int i = length/2-1;
        //构建堆
        while(i>=0){
            Sink(a,length,i);
            i--;
        }
        //堆排序
        for(int j = length-1;j>0;--j){
            swap(a[j],a[0]);
            Sink(a,j-1,0);
        }
    }
};

完整程序示例

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
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
#include <iostream>
using namespace std;
void display(int a[],int length){
    for(int i=0;i<length;++i){
        cout<<a[i]<<" ";
    }
    cout<<endl;
}
//选择排序
struct Selection{
    static void select(int a[],int length){  //不稳定
        cout<<"select sort"<<endl;
        for(int i=0;i<length;++i){
            int mindex = i;
            for(int j=i;j<length;++j){
                if(a[j]<a[mindex]) mindex = j;
            }
            swap(a[i],a[mindex]);
        }
    }
};
//冒泡排序
struct Bubble{
    static void bubble(int a[],int length){  //稳定
        cout<<"bubble sort"<<endl;
        for(int i=0;i<length;++i){
            for(int j=0;j<length-i-1;++j){
                if(a[j]>a[j+1]) swap(a[j],a[j+1]);
            }
        }
    }
};
//插入排序
struct Insert{
    static void insert(int a[],int length){   //稳定
        cout<<"insert sort"<<endl;
        for(int i=1;i<length;++i){
            //找到带插入位置
            int tem = a[i];
            int j;
            for(j=i-1;j>=0;--j){
                if(a[j]>tem){
                    a[j+1] = a[j];
                }else break;
            }
            a[j+1] = tem;
        }
    }
};
//希尔排序
struct Shell{
    static void shell(int a[],int length){   //不稳定
        cout<<"shell sort"<<endl;
        int h = 1;
        while(h<length/3) h = 3*h+1;   //增量分别为1,4,13,40,...
        while(h>=1){
            for(int i=h;i<length;++i){
                int tem = a[i];
                int j;
                for(j=i-h;j>=0;j-=h){
                    if(a[j]>tem){
                        a[j+h] = a[j];
                    }else break;
                }
                a[j+h] = tem;
            }
            h = h/3;
        }
    }
};
//递归归并排序
struct MergeSort{   //稳定
    static void Merge_sort(int a[],int low,int high,int aux[]){  //将[low,high]进行归并
        if(high<=low) return;
        int mid = low + (high-low)/2;
        Merge_sort(a,low,mid,aux);
        Merge_sort(a,mid+1,high,aux);
        Merge(a,low,mid,high,aux);
    }
    static void Merge(int a[],int low,int mid,int high,int aux[]){   //将[low,mid] 与 [mid+1,high]进行归并
        int i = low;
        int j = mid + 1;
        int index = low;
        while(i<=mid&&j<=high){
            if(a[i]<a[j]) aux[index++] = a[i++];
            else aux[index++] = a[j++];
        }
        while(i<=mid) aux[index++] = a[i++];
        while(j<=high) aux[index++] = a[j++];
        for(int k=low;k<=high;++k){
            a[k] = aux[k];
        }
    }
};
//非递归归并排序
struct NoRecMergeSort{   //稳定
    static norecMergeSort(int a[],int length,int aux[]){
        cout<<"norecMergeSort"<<endl;
        for(int sz = 1;sz<length;sz=sz+sz){
            for(int lo = 0;lo<length-sz;lo+=sz+sz){     //lo = lo + sz + sz
                Merge(a,lo,lo+sz-1,min(lo+sz+sz-1,length-1),aux);  // lo lo+sz-1  min(lo+sz+sz-1,length-1)
            }
        }
    }
    static void Merge(int a[],int low,int mid,int high,int aux[]){   //将[low,mid] 与 [mid+1,high]进行归并
        int i = low;
        int j = mid + 1;
        int index = low;
        while(i<=mid&&j<=high){
            if(a[i]<a[j]) aux[index++] = a[i++];
            else aux[index++] = a[j++];
        }
        while(i<=mid) aux[index++] = a[i++];
        while(j<=high) aux[index++] = a[j++];
        for(int k=low;k<=high;++k){
            a[k] = aux[k];
        }
    }
};
//快速排序
struct QuickSort{   //不稳定
    static void quicksort(int a[],int low,int high){    //对[low,high]进行快排
        if(high<=low) return;
        int j = Partition(a,low,high);
        quicksort(a,low,j-1);
        quicksort(a,j+1,high);
    }
    static int Partition(int a[],int low,int high){
        int i = low;
        int j = high + 1;
        int v = a[low];
        while(true){
            while(a[++i]<=v) {
                if(i==high) break;
            }
            while(a[--j]>=v) {
                if(j==low) break;
            }
            if(i>=j) break;
            swap(a[i],a[j]);
        }
        swap(a[low],a[j]);
        return j;
    }
};
//堆排序
struct HeapSort{   //大根堆
    static void Sink(int a[],int length,int index){   //数组下标为index的元素进行下沉操作
        while(2*index+1<length){  //有左孩子节点
            int big = 2*index+1;
            if((2*index+2<length) && (a[2*index+2]>a[2*index+1])) { big = 2*index+2; }  //右子节点存在且大于左子节点
            if(a[big]<=a[index]) break;  //已经有序，无须交换
            swap(a[index],a[big]);  //父节点和左右子节点中的较大值进行交换
            index = big;
        }
    }
    static void heapSort(int a[],int length){
        int i = length/2-1;
        //构建堆
        while(i>=0){
            Sink(a,length,i);
            i--;
        }
        //堆排序
        for(int j = length-1;j>0;--j){
            swap(a[j],a[0]);
            Sink(a,j-1,0);
        }
    }
};
int main()
{
    int a[] = {3,1,2,4,8,9,0,3,6,8,7};
    int aux[sizeof(a)/sizeof(a[0])] = {0};
    //Selection::select(a,sizeof(a)/sizeof(a[0]));
    //Bubble::bubble(a,sizeof(a)/sizeof(a[0]));
    //Insert::insert(a,sizeof(a)/sizeof(a[0]));
    //Shell::shell(a,sizeof(a)/sizeof(a[0]));
    //MergeSort::Merge_sort(a,0,sizeof(a)/sizeof(a[0])-1,aux);
    //NoRecMergeSort::norecMergeSort(a,sizeof(a)/sizeof(a[0]),aux);
    //QuickSort::quicksort(a,0,9);
    HeapSort::heapSort(a,sizeof(a)/sizeof(a[0]));
    display(a,sizeof(a)/sizeof(a[0]));
    return 0;
}
-------------本文结束感谢您的阅读-------------

本文地址：http://www.wangxinri.cn/2018/03/25/各种排序算法实现/
转载请注明出处，谢谢！

梦想夹带眼泪，咸咸的汗水！