排序算法（C++）

Posted on | In

排序算法（C++）

1
前言：要想成功，就别嫌自己笨
  • 主体学习框架参考 图解
  • 排序知识框架（待完善）
  • 排序相关复杂度
算法名称 平均时间复杂度 最好时间复杂度 最坏时间复杂度 空间复杂度 稳定性
冒泡排序 $O(n^2)$ $O(n)$ $O(n^2)$ $O(n1)$ 稳定
选择排序 $O(n^2)$ $O(n^2)$ $O(n^2)$ $O(n1)$ 不稳定
插入排序 $O(n^2)$ $O(n)$ $O(n^2)$ $O(n1)$ 稳定
希尔排序 $O(n^2)$ $O(n)$ $O(n^2)$ $O(n1)$ 不稳定
归并排序 $O(nlog2^n)$ $O(nlog2^n)$ $O(nlog2^n)$ $O(n)$ 稳定
快速排序 $O(nlog2^n)$ $O(nlog2^n)$ $O(n^2)$ $O(nlog2^n)$ 稳定
堆排序 $O(n^2)$ $O(n)$ $O(n^2)$ $O(n1)$ 稳定

冒泡排序

1. 思想：

一遍历一边把顺序错误的元素交换，等于一直找比自己大或者小的元素，一路放到最后,时间复杂度是$O(n^2)$

2. 实现
1
2
3
4
5
6
7
8
9
10
11
12
void bubbleSort(int* list){
    const int length = my_length(list);
    for(int i  = 0; i < length - 1; i++){
        for (int j = i; j < length - 1; j++) {
            if (list[i] > list[j+1]) {
                int temp = list[i];
                list[i] = list[j + 1];
                list[j + 1] = temp;
            }
        }
    }
}

选择排序

1. 思想：
2. 实现:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void selectionSort(int *list){
    const int length = my_length(list);
    int temp = 0;
    for (int i = 0; i < length -1; i++) {
        temp = i;
        for (int j = i + 1 ; j < length - 1; j++) {
            if(list[temp] > list[j]){
                temp = j;
            }
        }
        if (i != temp) {
            list[i] = list[i] + list[temp];
            list[temp] = list[i] - list[temp];
            list[i] = list[i] - list[temp];
            
        }
    }
}

插入排序

思想：

左边是一个有序的序列，每次有下标i去寻找在左边序列的位置。
平均时间复杂度是：$O(n^2)$
最坏时间复杂度是：$O(n^2)$
最好时间复杂度是：$O(n)$
空间复杂度是：$O(1)$

实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//起始端维持一个有序的序列
void insertSort(int* list, int length){
    for (int i = 1; i < length; i++){
        for (int j = i - 1; j >= 0; j--) {
            if (list[i] > list[j]) {
                break;
            }else{
                list[i] = list[i] + list[j];
                list[j] = list[i] - list[j];
                list[i] = list[i] - list[j];
                i = j;
            }
        }
    }
}

希尔排序

思想：
实现
1
2
3
4
5
6
7
8
9
10
11
12
void hillSort(int* list, int length){
    for(int i = length/2; i>= 1; i/=2) {
        for (int j = 0; j < length - i; j += 1){
            int next = j + i;
            if(list[j] > list[next]){
                list[next] = list[next] + list[j];
                list[j] = list[next] - list[j];
                list[next] = list[next] - list[j];
            }
        }
    }
}

归并排序

思想：

分治法，每个相邻的两个区间的值有序，则整个序列有序，区间用二分法，每次除以2
平均时间复杂度是：$O(n^2)$
最坏时间复杂度是：$O(n^2)$
最好时间复杂度是：$O(n)$
空间复杂度是：$O(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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
//并归排序
void doMerge(int *list, int start1, int end1, int start2, int end2){
    int x = start1;
    int y = start2;
    int list_index = 0;
    int length = end2 - start1 + 1;
    int templist[length];
    int temp_index;
    for (temp_index = 0 ; x <= end1 && y <= end2; temp_index++) {
        if(list[x] > list[y]){
            templist[temp_index] = list[y++];
        }else{
            templist[temp_index] = list[x++];
        }
    }
//    print_list(templist, length);
    while (x <= end1) {
        templist[temp_index++] = list[x++];
    }
    while (y <= end2) {
        templist[temp_index++] = list[y++];
    }

    list_index = 0;
    for (int j=start1; j <= end2; j++, list_index++) {
        list[j] = templist[list_index];
    }
}

void doMergeSort(int *list, int start, int end){
    if(start < end){
        int mid = (end + start) /2;
        doMergeSort(list, start, mid);
        doMergeSort(list, mid + 1, end);
//        cout << "start:" <<start << "n" << mid << "end" << end <<endl;
        doMerge(list, start, mid , mid + 1, end);
//        print_list(list, 15);
    }
}
void mergeSort(int *list){
    int length = 15;
    doMergeSort(list, 0, length - 1);
}

快速排序

思想：

分治法，每次取一个基准，一般是首位，小于基准的放左边，大于基准的放右边
平均时间复杂度是：$O(n^2)$
最坏时间复杂度是：$O(n^2)$
最好时间复杂度是：$O(n)$
空间复杂度是：$O(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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
//快速排序
//找下标，返回边界
//切分函数
int partition(int *list, int pivot, int start, int end){
    int i = start , j = end;
    while (i < j) {
        if(list[i] > list[pivot])
        {
            if (list[j] < list[pivot]) {
                sawp(list, j, i);
                i++;
                j--;
            }else{
                j--;
            }
        }else{
            i++;
        }
    }
    if(list[pivot] > list[i]){
        return i;
    }else{
        return i - 1;
    }
}
void do_quick(int *list, int start, int end){
    if(start < end){
        auto new_pivot = partition(list, start, start, end);
        if(start != new_pivot){
            list[new_pivot] = list[start] + list[new_pivot];
            list[start] = list[new_pivot] - list[start];
            list[new_pivot] = list[new_pivot] - list[start];
        }
//        print_list(list, 15);
        do_quick(list, start, new_pivot - 1);
        do_quick(list, new_pivot + 1, end);
        
    }
}

void quickSort(int *list, int length){
    do_quick(list, 0, length-1);
}

堆排序

思想：

利用大顶堆的原理，每次把最大的堆顶取出来，与堆的最后一个元素交换，再继续做大顶堆直至结束
平均时间复杂度是：$O(n^2)$
最坏时间复杂度是：$O(n^2)$
最好时间复杂度是：$O(n)$
空间复杂度是：$O(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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
//堆排序
void heap_swap(int *list, int j){
    int left = 2 * j +1;
    int right = 2 * j +2;
    if(list[left] > list[j]){
        sawp(list, left, j);
    }
    if(list[right] > list[j]){
        sawp(list, right, j);
    }else{
        return;
    }
}

void heap_reswap(int *list, int j){
    int father;
    while(j > 0){
        if (j % 2 == 1) {
             father = (j -1) / 2;
        }else{
             father = (j -2) / 2;
        }
        if(list[j] > list[father]){
            sawp(list, father, j);
            j = father;
        }else{
            break;
        }
    }
}

void heapSort(int *list, int length){
    for(int i = length - 1; i > 0 ;i--){
        for (int j = 0; j < i / 2 ; j++) {
            if(j == 0)
            {
                heap_swap(list, j);
            }else{
                heap_swap(list, j);
                heap_reswap(list, j);
            }
            
        }
        sawp(list, i, 0);
//        print_list(list, 15);
    }
}

计数排序

思想：

获得最大值，用最大值去构建一个数组，遍历列表一次，把命中下标的值加一，后面在遍历该数组，val有多少个，就拼多少个key给他
平均时间复杂度是：$O(n^2)$
最坏时间复杂度是：$O(n^2)$
最好时间复杂度是：$O(n)$
空间复杂度是：$O(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
25
26
27
28
29
30
31
//计数排序
void countingSort(int *list, int length){
    for (int j = 0; j < length / 2 ; j++) {
               if(j == 0)
               {
                   heap_swap(list, j);
               }else{
                   heap_swap(list, j);
                   heap_reswap(list, j);
               }
               
           }
    int max = list[0] + 1;
    int *templist = new int[max]();
    for (int i = 0; i < length; i++){
        int j = list[i];
        templist[j] += 1;
    }
    int index = 0;
    
    for(int i =0; i< max; i++){
        int j = templist[i];
        if (j == 0) {
            continue;;
        }else{
            for(int z = 0; z < j; z ++, index++){
                list[index] = i;
            }
        }
    }
}
非比较类排序讲原理，不写实现了

桶排序

思想：

原理正文
平均时间复杂度是：
最坏时间复杂度是：
最好时间复杂度是：
空间复杂度是：：

基数排序

思想：

原理正文
平均时间复杂度是：
最坏时间复杂度是：
最好时间复杂度是：
空间复杂度是：