排序算法(2)-c实现

理论请参考 排序算法

选择排序(Selection Sort)

#include <stdio.h>

void swap(int *x, int *y)
{
    int temp = *x;
    *x = *y;
    *y = temp;
}

int selection_sort(int *arr, int n)
{
    int i, j, min_i;

    for (i = 0; i < n - 1; i++) {
        min_i = i;

        //记录值最小的那个索引
        for (j = i+1; j < n; j++) {
            if (arr[j] < arr[min_i])
                min_i = j;
        }

        //交换
        if (i != min_i)
            swap(&arr[min_i], &arr[i]);
    }
}

int main(int argc, char **argv)
{
    int arr[] = {45,4,7,20,1001,35,100,2000,700,500,600,10,900,1000};
    int len = sizeof(arr)/sizeof(int);
    selection_sort(arr, len);
    return 0;
}

不用每次都交换,一次遍历只需要记录最小的那个索引,在一次遍历完之后只需交换一次即可 


冒泡排序(Bubble Sort)

#include <stdio.h>

void swap(int *x, int *y)
{
    int temp = *x;
    *x = *y;
    *y = temp;
}

void bubble_sort(int *arr, int n)
{
    int i, j, swaped;

    for (i = 0; i < n - 1; i++) {
        swaped = 0;

        for (j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j+1]) {
                swap(&arr[j], &arr[j+1]);
                swaped = 1;
            }
        }

        if (swaped == 0)
            break;
    }
}

void print_arr(int *arr, int n)
{
    int i;
    for (i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main(int argc, char **argv)
{
    int arr[] = {45,4,7,20,1001,35,100,2000,700,500,600,10,900,1000};
    int len = sizeof(arr)/sizeof(int);

    bubble_sort(arr, len);
    print_arr(arr, len);
    
    return 0;
}

这里有个优化

当数组已经排好序的情况 - O(n)

当数组是反向排序好的情况 - O(n^2)


插入排序(Insertion Sort)

#include <stdio.h>

// 排序好的     未排序好的
void insertion_sort(int *arr, int n)
{
    int i, j, key;

    for (i = 1; i < n; i++) {
        key = arr[i];   //右部没排序的第一个元素
        j = i - 1;      //存储左部排序好了的第一个元素,即最大元素

        while (key < arr[j] && j >= 0) {
            arr[j+1] = arr[j];  //往后挪一位
            j = j - 1;
        }
        
        //此时挪位完成,空出来的槽便可以存右部第一个新的元素 key
        arr[j+1] = key;
    }
}

void print_arr(int *arr, int n)
{
    int i;
    for (i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main(int argc, char **argv)
{
    int arr[] = {45,4,7,20,1001,35,100,2000,700,500,600,10,900,1000};
    int len = sizeof(arr)/sizeof(int);

    insertion_sort(arr, len);
    print_arr(arr, len);
    
    return 0;
}

时间复杂度:

1.已排序好的即最好情况 - O(n)

2.逆向排序好的即最坏情况 - O(n^2)

stable - sorting in palce


左部寻找插入点时现在是遍历,也可以改成 二分查找 寻找插入点,可以参考 搜索算法 自己实现


归并排序(Merge Sort)

#include <stdio.h>

//[l,m] [m+1,r]
void do_merge(int *arr, int l, int m, int r)
{
    int     n1, n2, n3, i, j, k;

    n1 = m - l + 1;
    n2 = r - m;

    // 创建左右2个临时数组并拷贝数据
    int     arr_l[n1], arr_r[n2];
    for (i = 0; i < n1; i++)
        arr_l[i] = arr[l+i];
    for (i = 0; i < n2; i++)
        arr_r[i] = arr[m+1+i];

    /*  2个临时数组都已经各自排序好
     *  所以可以交叉遍历比较,并存入 arr
     *  比如 {1,3,5}      {2,4,6,8}
     */

    i = 0;  // arr_l 索引
    j = 0;  // arr_r 索引
    k = l;  //原数组当前需要填充的索引

    while (i < n1 && j < n2) {
        if (arr_l[i] <= arr_r[j])
            arr[k++] = arr_l[i++];
        else
            arr[k++] = arr_r[j++];
    }

    // 处理余下的,下面两条语句只会执行一条
    while (i < n1) arr[k++] = arr_l[i++];
    while (j < n2) arr[k++] = arr_r[j++];

}

void merge_sort(int *arr, int l, int r)
{
    if (l >= r)
        return;

    int m = l + (r - l) / 2;

    merge_sort(arr, l, m);
    merge_sort(arr, m+1, r);

    do_merge(arr, l, m, r);
}

void print_arr(int *arr, int n)
{
    int i;
    for (i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main(int argc, char **argv)
{
    int arr[] = {45,4,7,20,1001,35,100,2000,700,500,600,10,900,1000};
    int len = sizeof(arr)/sizeof(int);

    merge_sort(arr, 0, len - 1);
    print_arr(arr, len);
    
    return 0;
}

空间复杂度 - O(n)

时间复杂度 - Θ(nLogn)

stable,not sort in place

归并排序一般是按顺序访问数据,所以对随机访问要求比较低,比较适合链表排序


快速排序(Quick Sort)

#include <stdio.h>

void swap(int *x, int *y)
{
    int temp = *x;
    *x = *y;
    *y = temp;
}

int partition(int *arr, int l, int r)
{
    int pivot = arr[r];
    int i = l;
    int j;

    for (j = l; j < r; j++) {
        if (arr[j] < pivot)
            swap(&arr[i++], &arr[j]);
    }

    //把 pivot 交换到最后一个i指向的位置
    swap(&arr[i], &arr[r]);

    return i;
}

void quick_sort(int *arr, int l, int r)
{
    if (l >= r)
        return;

    // 获取峰值索引 - 此时 arr[pi] 已经在正确的位置
    int pi = partition(arr, l, r);

    quick_sort(arr, l, pi - 1);
    quick_sort(arr, pi + 1, r);
    
}

void print_arr(int *arr, int n)
{
    int i;
    for (i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main(int argc, char **argv)
{
    int arr[] = {45,4,7,20,1001,35,100,2000,700,500,600,10,900,1000};
    int len = sizeof(arr)/sizeof(int);

    quick_sort(arr, 0, len - 1);
    print_arr(arr, len);
    
    return 0;
}

partion函数逻辑如下

假设 arr[] = {9 4 3 2 7 8 6}
初始 {ij9 4 3 2 7 8}  pivot = 6
j >= 6,所以 i 不动,j++  {i9 j4 3 2 7 8}
j < 6,所以j 交换到i,j++ i++ {4 i9 j3 2 7 8}
以此类推 {4 3 i9 j2 7 8}
{4 3 2 i9 j7 8}
{4 3 2 i9 7 j8}
{4 3 2 i9 7 8} - 此时遍历完成,把 pivot 放到 i 处即可
{4 3 2 6(pi) 7 8 9} - pi左边都是小鱼pi,右边都是大于pi


堆排序(Heap Sort)

#include <stdio.h>
#include <stdlib.h>

void swap(int *x, int *y) {int temp = *x; *x = *y; *y = temp;}

typedef struct {
    int     len;
    int     *arr;
} max_heap_t;

void max_heapify(max_heap_t *max_h, int i)
{
    int largest, left, right;

    largest = i;
    left = (i << 1) + 1;    //2i+1 - 左子节点
    right = (i + 1) << 1;   //2i+2 - 右子节点

    if (left < max_h->len && max_h->arr[left] > max_h->arr[largest])
        largest = left;

    if (right < max_h->len && max_h->arr[right] > max_h->arr[largest])
        largest = right;

    //如果需要调换,那么得把后面的节点重新堆化
    if (largest != i) {
        swap(&max_h->arr[largest], &max_h->arr[i]);
        max_heapify(max_h, largest);
    }
}

void heap_sort(int *arr, int len)
{
    int i;
    max_heap_t *max_h = malloc(sizeof(max_heap_t));
    max_h->arr = arr;
    max_h->len = len;

    //构建初始大顶堆,从底部第一个非叶子节点开始逐个往上堆化
    for (i = (len - 2) / 2; i >= 0; i--)
        max_heapify(max_h, i);

    //此时已经是大顶堆,堆顶即为最大值
    while (max_h->len > 1) {
        //将堆顶最大值放入到数组末尾
        swap(&max_h->arr[0], &max_h->arr[max_h->len - 1]);
        
        max_h->len--;   // 末尾元素已经是正确位置,可以排除了
        
        //重新调整为大顶堆
        max_heapify(max_h, 0);
    }
}

void print_arr(int *arr, int n)
{
    int i;
    for (i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main(int argc, char **argv)
{
    int arr[] = {100,50,4,6,8,5,9,14,50};
    int len = sizeof(arr)/sizeof(int);

    heap_sort(arr, len);
    print_arr(arr, len);
    
    return 0;
}

堆排序在现实当中很少用到,因为有 快速排序归并排序 更优,只是堆数据结构用的非常多


基数排序(Radix Sort)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//让 arr 以 arr[i] / exp % 10 的值从小到大排序,即以其中一个数字排序
void count_sort(int *arr, int len, int exp)
{
    int output[len],count[10],i;

    memset(count, 0, sizeof(int) * 10);

    for (i = 0; i < len; i++) {
        count[arr[i] / exp % 10]++;
    }

    for (i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }

    //必须从后往前遍历,需要保证稳定性
    for (i = len - 1; i >= 0; i--) {
        output[count[(arr[i]/exp%10)] - 1] = arr[i];
        count[(arr[i]/exp%10)]--;
    }

    //拷贝值
    for (i = 0; i < len; i++)
        arr[i] = output[i];

}

void radix_sort(int *arr, int len)
{
    int max,i,exp;

    max = arr[0];
    for (i = 1; i < len; i++) {
        if (arr[i] > max)
            max = arr[i];
    }

    for (exp = 1; max/exp > 0; exp *= 10)
        count_sort(arr, len, exp);
}

void print_arr(int *arr, int n)
{
    int i;
    for (i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main(int argc, char **argv)
{
    int arr[] = {100,50,44,16,28,5,9,14,50};
    int len = sizeof(arr)/sizeof(int);

    radix_sort(arr, len);
    print_arr(arr, len);
    
    return 0;
}


计数排序(Counting Sort)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define RANGE 256

void count_sort(char *arr, int len)
{
    int i;
    char output[len];
    char count[RANGE];

    memset(count, 0, RANGE);

    for (i = 0; i < len; i++)
        count[arr[i]]++;

    for (i = 1; i < RANGE; i++)
        count[i] += count[i - 1];

    //从后往前遍历,保证稳定性
    for (i = len - 1; i >= 0; i--) {
        output[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }

    //拷贝值
    for (i = 0; i < len; i++)
        arr[i] = output[i];

}

void print_arr(int *arr, int n)
{
    int i;
    for (i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main(int argc, char **argv)
{
    char str[] = "http://www.daileinote.com";
    int len = strlen(str);

    count_sort(str, len);
    printf("%s\n", str);
    
    return 0;
}

扩展下可以支持负数排序,但是不支持小数 计数排序对于数据范围很大的数组,需要大量时间和内存,计数排序是用来排序0到100之间的数字的最好的算法


桶排序(Bucket Sort)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct ele ele_t;
struct ele {
    int     n;
    ele_t   *next;
};

#define MAX 100

ele_t ** bucket_sort(ele_t *arr, int len)
{
    int i,j,index;
    int divisor = MAX / len + 1;

    ele_t **bucket = calloc(len * sizeof(void *), 1);

    ele_t   *cur,*old;

    for (i = 0; i < len; i++) {
        index = arr[i].n / divisor;
        
        //桶内排序,这里为了简便,使用最不好的遍历排序
        if (bucket[index]) {
            old = NULL;
            cur = bucket[index];

            while (cur->next && cur->n <= arr[i].n) {
                old = cur;
                cur = cur->next;
            }

            if (old) {
                if (cur->n <= arr[i].n)
                    cur->next = &arr[i];
                else {
                    old->next = &arr[i];
                    arr[i].next = cur;
                    //cur->next = NULL;
                }
            } else {
                if (cur->n <= arr[i].n)
                    cur->next = &arr[i];
                else {
                    bucket[index] = &arr[i];
                    arr[i].next = cur;
                }

            }

        } else
            bucket[index] = &arr[i];
    
    }

    ele_t   **res = malloc(len * sizeof(void *));
    
    i = 0;
    j = 0;

    for (i = 0; i < len; i++) {
        cur = bucket[i];

        while (cur) {
            res[j++] = cur;
            cur = cur->next;
        }
    }

    return res;
}

void print_arr(ele_t **arr, int n)
{
    int i;
    for (i = 0; i < n; i++) {
        printf("%d ", arr[i]->n);
    }
    printf("\n");
}

int main(int argc, char **argv)
{
    // 排序 0 - 100
    ele_t   e1 = {1, NULL};
    ele_t   e2 = {50, NULL};
    ele_t   e3 = {44, NULL};
    ele_t   e4 = {16, NULL};
    ele_t   e5 = {28, NULL};
    ele_t   e6 = {77, NULL};
    ele_t   e7 = {7, NULL};
    ele_t   e8 = {6, NULL};
    ele_t   e9 = {5, NULL};
    ele_t   e10 = {4, NULL};

    ele_t arr[] = {e1,e2,e3,e4,e5,e6,e7,e8,e9,e10};
    int len = sizeof(arr)/sizeof(ele_t);

    ele_t **res = bucket_sort(arr, len);
    print_arr(res, len);
    
    return 0;
}

工作的原理是将数组分到有限数量的桶里。每个桶再个别排序(当均匀分布时,这里需要比较次数将会最少)。当要被排序的数组内的数值是 均匀分配(uniformly distributed) 的时候,桶排序使用线性时间O(n)


鸽巢排序(Pigeonhole Sort)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct ele ele_t;
struct ele {
    int     n;
    ele_t   *next;
};

ele_t ** pigeonhole_sort(ele_t *arr, int len)
{
    int i,j,index,min,max,range;
    

    min = arr[0].n;
    max = min;
    for (i = 0; i < len; i++) {
        if (arr[i].n < min)
            min = arr[i].n;
        if (arr[i].n > max)
            max = arr[i].n;
    }

    range = max - min + 1;

    ele_t **bucket = calloc(range * sizeof(void *), 1);

    ele_t   *cur,*old;

    for (i = 0; i < len; i++) {
        index = arr[i].n - min;
        
        //相同的放到桶的最后来保持稳定
        if (bucket[index]) {
            cur = bucket[index];

            while (cur->next) {
                cur = cur->next;
            }

            cur->next = &arr[i];

        } else
            bucket[index] = &arr[i];
    
    }

    ele_t   **res = malloc(len * sizeof(void *));
    
    i = 0;
    j = 0;

    for (i = 0; i < range; i++) {
        cur = bucket[i];

        while (cur) {
            res[j++] = cur;
            cur = cur->next;
        }
    }

    return res;
}

void print_arr(ele_t **arr, int n)
{
    int i;
    for (i = 0; i < n; i++) {
        printf("%d ", arr[i]->n);
    }
    printf("\n");
}

int main(int argc, char **argv)
{
    // 排序 0 - 100
    ele_t   e1 = {1, NULL};
    ele_t   e2 = {50, NULL};
    ele_t   e3 = {44, NULL};
    ele_t   e4 = {16, NULL};
    ele_t   e5 = {28, NULL};
    ele_t   e6 = {77, NULL};
    ele_t   e7 = {7, NULL};
    ele_t   e8 = {6, NULL};
    ele_t   e9 = {5, NULL};
    ele_t   e10 = {4, NULL};

    ele_t arr[] = {e1,e2,e3,e4,e5,e6,e7,e8,e9,e10};
    int len = sizeof(arr)/sizeof(ele_t);

    ele_t **res = pigeonhole_sort(arr, len);
    print_arr(res, len);
    
    return 0;
}


希尔排序(Shell Sort)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void shell_sort(int *arr, int len)
{
    int temp,j,i;
    int gap = len / 2;

    for (; gap > 0; gap /= 2) {

        for (i = gap; i < len; i++) {
            temp = arr[i];

            //对列进行插入排序
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
                arr[j] = arr[j - gap];

            arr[j] = temp;
        }

    }

}

void print_arr(int *arr, int n)
{
    int i;
    for (i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main(int argc, char **argv)
{
    int arr[] = {100,50,44,16,28,5,9,14,50};
    int len = sizeof(arr)/sizeof(int);

    shell_sort(arr, len);
    print_arr(arr, len);
    
    return 0;
}


梳子排序(Comb Sort)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void swap(int *x, int *y) {int temp = *x; *x = *y; *y = temp;}
int get_gap(int gap) { gap = gap * 10 / 13; if (gap < 1) gap = 1; return gap;}

void comb_sort(int *arr, int len)
{
    int i;
    int gap = len;
    int swapped = 1;

    //当 gap==1 时,如果有交换发生,那么还需遍历验证
    while (gap != 1 || swapped) {
        gap = get_gap(gap);

        swapped = 0;

        for (i = 0; i < len - gap; i++) {
            if (arr[i] > arr[i + gap]) {
                swap(&arr[i], &arr[i + gap]);
                swapped = 1;
            }
        }
    }

}

void print_arr(int *arr, int n)
{
    int i;
    for (i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main(int argc, char **argv)
{
    int arr[] = {100,50,44,16,28,5,9,14,50};
    int len = sizeof(arr)/sizeof(int);

    comb_sort(arr, len);
    print_arr(arr, len);
    
    return 0;
}

时间复杂度:最好情况下 O(n),最差情况下 O(n^2)  

如同快速排序和合并排序,梳排序的效率在开始时最佳,接近结束时最差。如果间距变得太小时(例如小于10),改用插入排序或希尔排序等算法,可提升整体性能。 此方法最大好处是不需要检查是否进行过交换程序以将排序循环提早结束


圈排序(Cycle Sort)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void swap(int *x, int *y) {int temp = *x; *x = *y; *y = temp;}

void cycle_sort(int *arr, int n)
{
    int writes = 0;
    int cycle_start,pos,item,i;

    for (cycle_start = 0; cycle_start <= n - 2; cycle_start++) {
        item = arr[cycle_start];

        pos = cycle_start;

        for (i = cycle_start + 1; i < n; i++) {
            if (arr[i] < item)
                pos++;
        }

        //已经在正确位置,跳过
        if (pos == cycle_start)
            continue;

        //忽略相同的元素
        while (item == arr[pos])
            pos++;

        if (pos != cycle_start) {
            swap(&item, &arr[pos]);
            writes++;
        }

        while (pos != cycle_start) {
            pos = cycle_start;

            for (i = cycle_start + 1; i < n; i++) {
                if (arr[i] < item)
                    pos++;
            }

            while (item == arr[pos])
                pos++;

            if (item != arr[pos]) {
                swap(&item, &arr[pos]);
                writes++;
            }
        }


    }



}

void print_arr(int *arr, int n)
{
    int i;
    for (i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main(int argc, char **argv)
{
    int arr[] = {100,50,44,16,28,5,9,14,100};
    int len = sizeof(arr)/sizeof(int);

    cycle_sort(arr, len);
    print_arr(arr, len);
    
    return 0;
}

性能差,只有在数据写入开销非常大的情况适用,圈算法可以保证在正确位置的元素不动。

理论请参考 排序算法


参考:

算法导论

geeksforgeeks 


上一篇: 排序算法(1)
下一篇: 排序算法(3)-特征记录
作者邮箱: 203328517@qq.com