Benature
0%

排序算法

Posted on Edited on

排序 Sort

动画

  • 算法复杂度
    算法复杂度

总览

排序方法 排序方法 迭代方式 时间复杂度（平均）
冒泡排序 相邻比较+换位 for×2 $O(n^2)$
选择排序 向后查找最小元, 与每一轮首(i)位换位 for×2 $O(n^2)$
插入排序 从第二个开始抽出来, 和前面的比较并排位（向前比较然后插入） for×2 $O(n^2)$
希尔排序 按增量分批做 插入排序 for×3 $O(n^{1.3})$
快速排序 分块排序, 且左块皆小于右块 递归 $O(n\log_2n)$

冒泡排序 Bubble

相邻比较+换位

1
2
3
4
5
6
7
8
9
10
11
12
13
void BubbleSort(int *arr, int len)
{
    int i, j, tmp;
    for (i = 0; i < len - 1; i++) {
        for (j = 0; j < len - i - 1; j++) {
            if (arr[j] > arr[j+1]) {
                tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
            }
        }
    }
}

冒泡

👆

选择排序 Select

向后查找最小元, 与每一轮首位换位

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void SelectionSort(int *arr, int len)
{
    int i, j, min, tmp;
    for (i = 0; i < len - 1; i++) {
        min = i;
        for (j = i + 1; j < len; j++) {
            if (arr[j] < arr[min]) {
                min = j;// 修改最小元
            }
        }
        tmp = arr[min];
        arr[min] = arr[i];
        arr[i] = tmp;
    }
}

选择

👆

插入排序 Insert

从第二个开始抽出来, 和前面的比较并排位（向前比较然后插入）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void InsertionSort(int *arr, int len)
{
    int tmp;
    for (int i = 1; i < len; i++) {
        //从第二个开始
        if (arr[i] < arr[i-1]) {   // 如果小于前一个 // 其实这个判断不要应该也行，后面的 for 结束条件可以囊括
            tmp = arr[i];          // 要移动的元放到temp中
            for (int j = i - 1; j >= 0 && arr[j] > tmp; j--) {
                // 结束条件：当第一次 arr[j] < tmp 说明到达了要插入的位置
                arr[j+1] = arr[j]; //向前顺位
            }
            arr[j+1] = tmp;
        }
    }
}

插入

👆

希尔排序 Shell

按增量分批做插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 希尔排序
void ShellSort(int *arr, int size)
{
    int i, j, tmp, increment;
    // 先选定增量
    for (increment = size/ 2; increment > 0; increment /= 2) {
        // 直到除 2 为 0（即最后一次 increment = 1）

        // ========v 插入排序部分 v========
        // 从第二批增量 batch 开始遍历数组
        for (i = increment; i < size; i++) {
            // 做插入排序
            tmp = arr[i];
            // 先前遍历
            for (j = i - increment; j >= 0 && tmp < arr[j]; j -= increment) {
                arr[j + increment] = arr[j];
            }
            arr[j + increment] = tmp;
        }
        // ========^ 插入排序部分 ^========
    }
}

希尔

👆

归并排序 Merge

分治法

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
void merge(int arr[], int low, int mid, int high){
    int i, k;
    int *tmp = (int *)malloc((high-low+1)*sizeof(int));
    //申请空间，使其大小为两个
    int left_low = low;
    int left_high = mid;
    int right_low = mid + 1;
    int right_high = high;

    for(k=0; left_low<=left_high && right_low<=right_high; k++){  // 比较两个指针所指向的元素
        if(arr[left_low]<=arr[right_low]){
            tmp[k] = arr[left_low++];
        }else{
            tmp[k] = arr[right_low++];
        }
    }

    if(left_low <= left_high){  //若第一个序列有剩余，直接复制出来粘到合并序列尾
        //memcpy(tmp+k, arr+left_low, (left_high-left_low+l)*sizeof(int));
        for(i=left_low;i<=left_high;i++)
            tmp[k++] = arr[i];
    }

    if(right_low <= right_high){ //若第二个序列有剩余，直接复制出来粘到合并序列尾
        //memcpy(tmp+k, arr+right_low, (right_high-right_low+1)*sizeof(int));
        for(i=right_low; i<=right_high; i++)
            tmp[k++] = arr[i];
    }

    // 从tmp复制回arr内
    for(i=0; i<high-low+1; i++)
        arr[low+i] = tmp[i];
    free(tmp);
    return;
}

void MergeSort(int arr[], unsigned int first, unsigned int last){
    int mid = 0;
    if(first<last){
        mid = (first+last)/2; /* 注意防止溢出 */
        /*mid = first/2 + last/2;*/
        //mid = (first & last) + ((first ^ last) >> 1);
        MergeSort(arr, first, mid);
        MergeSort(arr, mid+1,last);
        merge(arr,first,mid,last);
    }
    return;
}

👆

快速排序 Quick

分块排序, 且左块皆小于右块

  • 形式 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
void swap(int *a, int *b){
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

void QuickSort(int *arr, int maxlen, int begin, int end)
{
    // printf("\nQuickSort(%d->%d)\n", begin, end);
    if (end - begin < 0){ return; } // 应该可以再加个等号？

    // arr[begin] 为轴心点（与他比较）（亮黄色）
    int store = begin + 1; // 存储指数（紫色第一个）
    int i = begin + 1;     // 试探（红色）

    // 把比轴心点（arr[begin]）要小的数据全部移动到紧贴轴心点的右侧
    while (i < end){
        if (arr[i] < arr[begin]){
            swap(&arr[i], &arr[store]); // 移动过去的都是比轴心点小的
            store++; // 自增，指向下一个准备交换的位置
            // 数据点变绿
        }
        i++;
    }

    swap(&arr[store - 1], &arr[begin]); // 轴心点数值跳到那些都比他小的最右
    // printf("\n");

    // 左右递归
    QuickSort(arr, maxlen, begin, store - 1);
    QuickSort(arr, maxlen, store, end);
}

快速

  • 形式 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void QuickSort(int *arr, int maxlen, int begin, int end){
    int i, j;
    if (begin < end) {
        // arr[begin]为轴心点（与他比较）
        i = begin + 1;
        j = end;
        while (i < j) {
            if(arr[i] > arr[begin]) {
                swap(&arr[i], &arr[j]);
                j--;
            } else {
                i++;        // 否则继续往后看
            }
        }                   // 循环跳出后i,j一样
        if (arr[i] >= arr[begin]) {
            i--;
        }
        swap(&arr[begin], &arr[i]);
        QuickSort(arr, maxlen, begin, i);
        QuickSort(arr, maxlen, j, end);
    }
}

👆

堆排序 Heap

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
#define LeftChild(i) (2*(i)+1)

void PercDown(int A[],int i, int N){                  // 下滤
    int Child;
    int Tmp;
    for (Tmp=A[i];LeftChild(i)<N;i=Child){            // Tmp为第一个本体的值 , 每次更新i为指向的子节点(较大者)
        Child = LeftChild(i);                         // 指向左子节点
        if(Child != N-1 && A[Child + 1] > A[Child]){  // 子节点不在最末(不然会爆) 且 右子节点>左子节点
            Child++;                                  // 从左子节点指向右子节点
        }
        if(Tmp < A[Child]){                           // 如果本体小于子节点最大的那个,
            A[i] = A[Child];                          // 把子节点覆盖到本体.
        }else{
            break;                                    // 一旦本体已经最大则跳出
        }
    }
    A[i] = Tmp;                                       // 把元初本体的值放到最后指向的子节点
}

void HeapSort(int A[],int N){
    int i;
    for (i=N/2;i>=0;i--){                             // 从倒数第二层向上过滤排序
        PercDown(A,i,N);                              // 构造大顶堆
    }
    for (i = N-1;i>0;i--){
        swap(&A[0],&A[i]);                            // 每换一次位(提取最大值到最后),
        PercDown(A,0,i);                              // 又要再做一次下滤.
    }
}

堆

👆

基数排序

1
// TODO: 略

基数

👆

计数排序

1
// TODO: 略

计数

👆

桶排序

1
// TODO: 略

桶

👆

随机快速排序

1
// TODO: 略

👆