直接插入排序

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
//插入排序
// Created by Kelen Hooper on 2020/12/22.
//
#include<iostream>
using namespace std;

void InsertSort(int *L, int left, int right){
        for(int i= left+1;i<=right;i++){
            if(L[i]<L[i-1]){
               int j=i-1,temp=L[i];
               do{
                   L[j+1] = L[j];
                   j = j-1;
               }while(j>=left && temp<L[j]);
               L[j+1] = temp;
            }
        }
}
int main(){
    int n;
    cin >> n;
    int *L = new int[n];
    for(int k=0;k<n;k++){
        cin >> L[k];
    }
    InsertSort(L,0,n-1);
    for(int i=0; i<n; i++){
        cout << L[i]<< " ";
    }
}

折半插入排序

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
//折半插入排序
// Created by Kelen Hooper on 2020/12/22.
//
#include <iostream>
using namespace std;
void BinaryInsertSort(int *L, int left, int right){
    for(int i=left+1;i<=right;i++){
        //cout<<i<<endl;
        int temp=L[i], low=left, high=i-1;
        while(low<=high){
            int mid = (low+high)/2;
            if(temp<L[mid]) high=mid-1;
            else low=mid+1;
        }
        for(int j=i-1;j>=low;j--){
            L[j+1]= L[j];
        }
        L[low] = temp;
    }
}
int main(){
    int n;
    cin >> n;
    int *L = new int[n];
    for(int k=0;k<n;k++){
        cin >> L[k];
    }
    BinaryInsertSort(L,0,n-1);
    for(int i=0; i<n; i++){
        cout << L[i]<< " ";
    }
}

希尔排序

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
//希尔排序
// Created by Kelen Hooper on 2020/12/22.
//
#include <iostream>
using namespace std;

void ShellSort(int *L, int left, int right){
    int gap = right - left + 1;
    do{
        gap = gap/3+1;
        for(int i= left+gap; i<=right; i++){
            if(L[i]<L[i-gap]){
                int temp=L[i],j= i-gap;
                do{
                    L[j+gap] = L[j];
                    j=j-gap;
                }while(j>=left && temp<L[j]);//j>=left要有等号，可以试一下去掉等号，6，2，1，gap=gap/4+1
                L[j+gap] = temp;
            }
        }
    }while(gap>1);
}
int main(){
    int n;
    cin >> n;
    int *L = new int[n];
    for(int k=0;k<n;k++){
        cin >> L[k];
    }
    ShellSort(L,0,n-1);
    for(int i=0; i<n; i++){
        cout << L[i]<< " ";
    }
}

冒泡排序

归并排序

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
//冒泡排序
// Created by Kelen Hooper on 2020/12/22.
//
#include<iostream>
using namespace std;
void BubbleSort(int *L, int n){
    for(int i=1;i<n;i++){
//        cout<<i<<endl;
        bool flag=false;
        for(int j=n-1;j>=i;j--){
            if(L[j]<L[j-1]) {
                swap(L[j],L[j-1]);
                flag=true;
            }
        }
//        for(int i=0; i<n; i++){
//            cout << L[i]<< " ";
//        }
//        cout<<endl;
        if(flag == false) return;
    }

}
int main(){
    int n;
    cin >> n;
    int *heap = new int[n];

    for(int k=0;k<n;k++){
        cin >> heap[k];
    }
    BubbleSort(heap,n);
    for(int i=0; i<n; i++){
        cout << heap[i]<< " ";
    }
}

/*
 intput:
        10
        2 4 1 5 6 3 10 8 9 7
 output:
        1 2 3 4 5 6 7 8 9 10
 */

快速排序

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
//快速排序
// Created by Kelen Hooper on 2020/7/22.
//
#include<iostream>
using namespace std;

int Partition(int *L, int left, int right){
    int pivotpos = left, pivot = L[left];
    for(int i=left+1; i<= right; i++){
        if(L[i]<pivot){ //一直都是跟基准元素比较，
            pivotpos++;//为的是把大于和小于基准元素的分放到两边
            if(pivotpos!=i){
                swap(L[pivotpos],L[i]);
            }
        }
    }
    L[left] = L[pivotpos];L[pivotpos]=pivot;

    return pivotpos;
}

void QuickSort(int *L, int left, int right){
    if(left<right){
        int pos = Partition(L, left, right);
        QuickSort(L, left, pos-1);
        QuickSort(L, pos+1, right);
    }
}

int main(){
    int n;
    cin >> n;
    int *L = new int[n];
    for(int k=0;k<n;k++){
        cin >> L[k];
    }
    QuickSort(L,0,n-1);
    for(int i=0; i<n; i++){
        cout << L[i]<< " ";
    }
}

简单选择排序

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
//简单选择排序
// Created by Kelen Hooper on 2020/12/22.
//

#include<iostream>
using namespace std;
void SlectSort(int *L, int left, int right){
    for(int i=left;i<right;i++){
        int k=i;
        for(int j=i+1;j<=right;j++){
            if(L[j]<L[k]) k=j;
        }
        if(i!=k) swap(L[i],L[k]);
    }
}
int main(){
    int n;
    cin >> n;
    int *heap = new int[n];

    for(int k=0;k<n;k++){
        cin >> heap[k];
    }
    SlectSort(heap,0,n-1);
    for(int i=0; i<n; i++){
        cout << heap[i]<< " ";
    }
}

/*
 intput:
        10
        2 4 1 5 6 3 10 8 9 7
 output:
        1 2 3 4 5 6 7 8 9 10
 */

堆排序

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
//堆排序
// Created by Kelen Hooper on 2020/12/22.
//
#include<iostream>
using namespace std;
void siftDown(int *heap , int start , int m){
    int i=start , j= i*2+1 ;
    int temp = heap[start];
    while(j<=m){
        if(j<m && heap[j]<heap[j+1]) ++j;
        if(temp>=heap[j]) break;//一直都是和顶元素比较，
                    //下面也只是子大孩子上移，而顶元素不下移
        else{
            heap[i] = heap[j];
            i=j;j=j*2+1;
        }

    }
    heap[i] = temp;
}
void HeapSort(int *heap, int currentSize){
    for(int i=(currentSize-2)/2;i>=0; i--){
        siftDown(heap, i, currentSize-1);
    }
    for(int i= currentSize-1; i>0; i--){
        swap(heap[0],heap[i]);
        siftDown(heap, 0, i-1);
    }
}
int main(){
    int n;
    cin >> n;
    int *heap = new int[n];

    for(int k=0;k<n;k++){
        cin >> heap[k];
    }
    HeapSort(heap,n);
    for(int i=0; i<n; i++){
        cout << heap[i]<< " ";
    }
}
/*
 intput:
        10
        2 4 1 5 6 3 10 8 9 7
 output:
        1 2 3 4 5 6 7 8 9 10
 */

归并排序

归并排序

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
//归并排序
// Created by Kelen Hooper on 2020/7/18.
//

#include<iostream>
using namespace std;
void merge(int *L1,int *L2,const int left, const int mid, const int right){
    for(int k=left; k<=right; k++){
        L2[k]= L1[k];
    }
    int s1 = left, s2 = mid +1 ;
    int t = left;
    while(s1<=mid && s2<=right){
        if(L2[s2] < L2[s1]) L1[t++] = L2[s2++];
        else L1[t++] = L2[s1++];
    }
    while(s1<=mid) L1[t++] = L2[s1++];
    while(s2<=right) L1[t++] = L2[s2++];
}
void MergeSort(int *L, int *L2, int left, int right){
    if(left >= right) return;
    int mid = (left+right)/2;
    MergeSort(L,L2,left,mid);
    MergeSort(L,L2,mid+1,right);
    merge(L,L2,left,mid,right);
}
int main(){
    int n;
    cin >> n;
    int *L = new int[n];
    int *L2 = new int[n];
    for(int k=0;k<n;k++){
        cin >> L[k];
        L2[k] = 0;
    }
    MergeSort(L,L2,0, n-1);
    for(int i=0; i<n; i++){
        cout << L[i]<< " ";
    }
}

/*
intput: 2 4 1 5 6 3 10 8 9 7
output: 1 2 3 4 5 6 7 8 9 10

 */