排序算法

// 插入排序：假设数组有n个元素，i = 1:n，若i < i-1，则交换两者，直到使得1到i的数组有序递增。时间复杂度O(N^2)
int *InsertSort(int ary[], int n){

    
    int i, j, z = 0;
    
    for (i = 1; i < n; i++) {
        for (j = i; j > 0; j--) {
            if (ary[j] < ary[j - 1]) {
                swap(&ary[j], &ary[j - 1]);
            } else {// 当i>=i-1时，接下去的比较无意义
                break;
            }
        }
    }
    
    return ary;
}

// 选择排序：假设数组长度为n，i=1:n，从i+1到n中选择最小的一个和i交换。时间复杂度O(N^2)
int *SelectionSort(int ary[], int n){

    
    int i, j, k, z = 0;
    
    for (i = 0; i < n; i++) {
        for (k = i, j = i + 1; j < n; j++) {
            if (ary[k] > ary[j]) {
                k = j;
            }
        }
        swap(&ary[i], &ary[k]);
    }
    
    return ary;
}

// 冒泡排序：假设数组长度为n，i=1:n-1，若i>i+1，则交换两者，直到使得1到n的数组有序递增。时间复杂度O(N^2)
int *BubbleSort(int ary[], int n){

    
    int i, j, z = 0;
    
    int swapped = 0;
    
    for (i = 0; i < n; i++) {
        for (j = n - 1; j > i; j--) {
            if (ary[j] < ary[j - 1]) {
                swap(&ary[j], &ary[j - 1]);
                swapped = 1;
            }
        }
        if (!swapped) break;
    }
    
    return ary;
}

// 堆排序：假设数组长度为n，i=1:n/2-1，若i<2i，则交换两者，若i<2i+1，则交换两者，直到i=0结束，交换0和n-1的元素。n=n-1，重复操作，直到n=2。时间复杂度O(nlgn)
int *HeapSort(int ary[], int n, int total){

    
    int i;
    
    for (i = n / 2 - 1; i >= 0; i--) {
        if (ary[i] < ary[2 * i]) swap(&ary[i], &ary[2 * i]);
        if (ary[i] < ary[2 * i + 1]) swap(&ary[i], &ary[2 * i + 1]);
    }
    
    swap(&ary[0], &ary[n - 1]);
    
    if (n > 1) HeapSort(ary, n - 1, total);
    
    return ary;
}

// 希尔排序：假设数组长度为n，步长g循环n>>1，i=g:n，为所有的j = i-g loop, j > 0做排序。
int *ShellSort(int ary[], int n){


    int gap, i, j, temp;

    for (gap = n >> 1; gap > 0; gap >>= 1) {
        for (i = gap; i < n; i++) {
            temp = ary[i];
            for (j = i - gap; j >= 0 && ary[j] > temp; j -= gap) {
                ary[j + gap] = ary[j];
            }
            ary[j + gap] = temp;
        }
    }
    
    return ary;
}

// 快速排序
void _QuickSort(int ary[], int start, int end)
{

    if (start >= end) return;
    
    int l = start, r = end - 1;
    
    while (l < r) {
        while (l < r && ary[l] < ary[end]) ++l;
        while (l < r && ary[r] >= ary[end]) --r;
        if (l != r) swap(&ary[l], &ary[r]);
        printf("111本次排序结果：\n");
        printf("l: %d, r: %d, s: %d, e: %d\n", l, r, start, end);
        printArray(ary, 10);
        printf("\n");
    }
    
    if (ary[l] > ary[end]) swap(&ary[end], &ary[l]);
    else l++; // l++是为了保护已经在有序位上的元素，例如为8，7，9排序，l指向7的索引1，但明显9最大，9后面没有更多的数据需要排序，仅需要对8和7做排序，因此l++，使得l的值为2，仅对8，7做排序
    
    printf("222本次排序结果：\n");
    printf("l: %d, r: %d, s: %d, e: %d\n", l, r, start, end);
    printArray(ary, 10);
    printf("\n");
    _QuickSort(ary, start, l - 1);
    _QuickSort(ary, l + 1, end);
    
    return;
}

int *QuickSort(int ary[], int n){


    _QuickSort(ary, 0, n - 1);
    
    return ary;
}

// 未完，待续。。。

交换排序

冒泡排序

算法描述

假设数组ary长度为N，i=0:N-1，j=N-1:i+1，如果ary[j-1] > ary[j]，则swap(ary[j - 1], ary[j]);

算法

算法实现

鸡尾酒排序

鸡尾酒排序是冒泡排序的一个变种，冒泡排序是一个方向从头排到尾，鸡尾酒排序是双向同时排序。

算法描述

假设数组ary长度为N，无限循环做以下处理，i=0:N-2，如果ary[i]大于ary[i + 1]，则swap(ary[i], ary[i + 1])，设置swapped=true，退出i的循环；j=N-2:0，如果ary[j]大于ary[j + 1]，则swap(ary[j], ary[j + 1])，设置swapped=true，退出j的循环。如果swapped!=true，说明已经有序，则退出无限循环。

奇偶排序

奇偶排序是一个不断比较左右两个值大小的算法，当左值大于右值时，做交换操作，直到交换不再发生，则排序结束。

算法描述

假设数组ary长度为N，无限循环做以下处理，i=0:1，j=i:N-1;step=2，若ary[j]大于ary[j + 1]则交换两者，swapped赋值为true，当swapped不为true时，退出无限循环。

梳排序

侏儒排序

桶排序

假设数组有N个元素，初始化M（M根据情况决定）个桶，将N个元素根据规则放入M个桶内，并排好序，最后将所有桶合并并排序。