排序算法

Posted on Edited on Views: Valine:

排序 Sort

动画

  • 算法复杂度
    算法复杂度

    冒泡排序 Bubble

    相邻比较+换位
    1
    void BubbleSort(int *arr, int len)  
    2
    {  
    3
        int i, j, tmp;  
    4
        for (i = 0; i < len - 1; i++) {  
    5
            for (j = 0; j < len - i - 1; j++) {  
    6
                if (arr[j] > arr[j+1]) {  
    7
                    tmp = arr[j];  
    8
                    arr[j] = arr[j+1];  
    9
                    arr[j+1] = tmp;  
    10
                }  
    11
            }  
    12
        }  
    13
    }  
    14
    ``` 
    15
    ![冒泡](algorithm-sort/BubbleSort.gif)
    16
    17
    ## 选择排序 Select
    18
    向后查找最小元, 与每一轮首位换位
    19
    ```c 
    20
    void SelectionSort(int *arr, int len)
    21
    {
    22
        int i, j, min, tmp;
    23
        for (i = 0; i < len - 1; i++) {
    24
            min = i;
    25
            for (j = i + 1; j < len; j++) {
    26
                if (arr[j] < arr[min]) {
    27
                    min = j;// 修改最小元
    28
                }
    29
            }
    30
            tmp = arr[min];
    31
            arr[min] = arr[i];
    32
            arr[i] = tmp;
    33
        }
    34
    }
    选择

插入排序 Insert

从第二个开始抽出来, 和前面的比较并排位

1
void InsertionSort(int *arr, int len)    
2
{    
3
    int i, j, tmp;    
4
    for (i = 1; i < len; i++) { 
5
        //从第二个开始   
6
        if (arr[i] < arr[i-1]) {   // 如果小于前一个 
7
            tmp = arr[i];          // 要移动的元放到temp中
8
            for (j = i - 1; j >= 0 && arr[j] > tmp; j--) {  
9
                //向前顺位
10
                arr[j+1] = arr[j];    
11
            }  
12
            arr[j+1] = tmp;    
13
        }          
14
    }    
15
}

插入

希尔排序 Shell

按增量分批做插入排序

1
// 希尔排序
2
void ShellSort(int *arr, int size)  
3
{  
4
    int i, j, tmp, increment;  
5
    for (increment = size/ 2; increment > 0; increment /= 2) {    
6
        for (i = increment; i < size; i++) {  
7
            // 做插入排序
8
            tmp = arr[i];  
9
            for (j = i - increment; j >= 0 && tmp < arr[j]; j -= increment) {  
10
                arr[j + increment] = arr[j];  
11
            }  
12
            arr[j + increment] = tmp;
13
        }  
14
    }  
15
}

希尔

归并排序 Merge

分治法

1
void merge(int arr[], int low, int mid, int high){
2
    int i, k;
3
    int *tmp = (int *)malloc((high-low+1)*sizeof(int));
4
    //申请空间，使其大小为两个
5
    int left_low = low;
6
    int left_high = mid;
7
    int right_low = mid + 1;
8
    int right_high = high;
9
10
    for(k=0; left_low<=left_high && right_low<=right_high; k++){  // 比较两个指针所指向的元素
11
        if(arr[left_low]<=arr[right_low]){
12
            tmp[k] = arr[left_low++];
13
        }else{
14
            tmp[k] = arr[right_low++];
15
        }
16
    }
17
18
    if(left_low <= left_high){  //若第一个序列有剩余，直接复制出来粘到合并序列尾
19
        //memcpy(tmp+k, arr+left_low, (left_high-left_low+l)*sizeof(int));
20
        for(i=left_low;i<=left_high;i++)
21
            tmp[k++] = arr[i];
22
    }
23
24
    if(right_low <= right_high){ //若第二个序列有剩余，直接复制出来粘到合并序列尾
25
        //memcpy(tmp+k, arr+right_low, (right_high-right_low+1)*sizeof(int));
26
        for(i=right_low; i<=right_high; i++)
27
            tmp[k++] = arr[i];
28
    }
29
30
    // 从tmp复制回arr内
31
    for(i=0; i<high-low+1; i++)
32
        arr[low+i] = tmp[i];
33
    free(tmp);
34
    return;
35
}
36
37
void MergeSort(int arr[], unsigned int first, unsigned int last){
38
    int mid = 0;
39
    if(first<last){
40
        mid = (first+last)/2; /* 注意防止溢出 */
41
        /*mid = first/2 + last/2;*/
42
        //mid = (first & last) + ((first ^ last) >> 1);
43
        MergeSort(arr, first, mid);
44
        MergeSort(arr, mid+1,last);
45
        merge(arr,first,mid,last);
46
    }
47
    return;
48
}

快速排序 Quick

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

  • 形式 1 （对应动图）
1
void swap(int *a, int *b){  
2
    int temp;  
3
    temp = *a;  
4
    *a = *b;  
5
    *b = temp;  
6
}  
7
void QuickSort(int *arr, int maxlen, int begin, int end){  
8
void QuickSort(int *arr, int maxlen, int begin, int end)
9
{
10
    printf("\nQuickSort(%d->%d)\n", begin, end);
11
    int i, store;
12
    if (begin - end >= -1){
13
        return;
14
    }
15
    // arr[begin]为轴心点（与他比较）（亮黄色）
16
    i = begin + 1;     // 试探（红色）
17
    store = begin + 1; // 存储指数（紫色最左）
18
    while (i < end){
19
        if (arr[i] < arr[begin]){
20
            swap(&arr[i], &arr[store]); // 移动过去的都是比轴心点小的
21
            store++; // 指向的是不满足判断条件的那个点（比轴心点大）
22
        }
23
        i++;
24
    }
25
26
    swap(&arr[store - 1], &arr[begin]); // 轴心点数值跳到那些都比他小的最右
27
    printf("\n");
28
    QuickSort(arr, maxlen, begin, store - 1);
29
    QuickSort(arr, maxlen, store, end);
30
}

快速

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

堆排序 Heap

1
#define LeftChild(i) (2*(i)+1)
2
3
void PercDown(int A[],int i, int N){                  // 下滤
4
    int Child;
5
    int Tmp;
6
    for (Tmp=A[i];LeftChild(i)<N;i=Child){            // Tmp为第一个本体的值 , 每次更新i为指向的子节点(较大者)
7
        Child = LeftChild(i);                         // 指向左子节点
8
        if(Child != N-1 && A[Child + 1] > A[Child]){  // 子节点不在最末(不然会爆) 且 右子节点>左子节点
9
            Child++;                                  // 从左子节点指向右子节点
10
        }
11
        if(Tmp < A[Child]){                           // 如果本体小于子节点最大的那个,
12
            A[i] = A[Child];                          // 把子节点覆盖到本体.
13
        }else{
14
            break;                                    // 一旦本体已经最大则跳出
15
        }
16
    }
17
    A[i] = Tmp;                                       // 把元初本体的值放到最后指向的子节点
18
}
19
20
void HeapSort(int A[],int N){
21
    int i;
22
    for (i=N/2;i>=0;i--){                             // 从倒数第二层向上过滤排序
23
        PercDown(A,i,N);                              // 构造大顶堆
24
    }
25
    for (i = N-1;i>0;i--){
26
        swap(&A[0],&A[i]);                            // 每换一次位(提取最大值到最后),
27
        PercDown(A,0,i);                              // 又要再做一次下滤.
28
    }
29
}

堆

基数排序

1
// TODO: 略

基数

计数排序

1
// TODO: 略

计数

桶排序

1
// TODO: 略

桶

随机快速排序

1
// TODO: 略