排序算法

常见排序的一些最优写法的收集。

冒泡排序

// 借助 sorted，可提前判断有序退出
void bubble_sort( int *begin, int *end )
{
    bool sorted = false; // 假定尚未排序
    while( ! sorted )
    {
        sorted = true; // 假定已经有序
        for( int *i = begin; i < end; i++ ) // 依次检查相邻元素是否有序
        {
            if( *i > *( i + 1 ) ) // 一旦逆序，则交换之
            {
                swap( i, i + 1 );
                sorted = false; // 不能保证整体有序，故设置false
            }
        }
        end--;
    }
}

选择排序(非稳定)

int* sortArray(int* nums, int numsSize, int* returnSize)
{
    int min = 0;
    int cur = 0;
    int j = 0;
    for( cur = 0; cur < numsSize - 1; cur ++ )
    {
        for(min = cur,  j = min + 1; j < numsSize; j++ )
        {
            if( nums[j] < nums[min] )
                min = j;
        }
        int tmp = nums[cur];
        nums[cur] = nums[min];
        nums[min] = tmp;
    }
    *returnSize = numsSize;
    return nums;
}

插入排序

int* sortArray(int* nums, int numsSize, int* returnSize)
{
    int insert_idx;
    int insert_num;
    for(  int tail = 1; tail < numsSize; tail++ )
    {
        insert_num = nums[tail];
        for( insert_idx = tail; 0 < insert_idx; insert_idx --  )
        {
            if( nums[insert_idx - 1] <= insert_num )
                break;
            else
                nums[insert_idx] = nums[insert_idx - 1];
        }
        // 优先确定index_idx就是我们要写的下标，然后再写内循环每次返回一个下标，逻辑会顺畅很多
        nums[insert_idx] = insert_num;
    }
    *returnSize = numsSize;
    return nums;
}

快速排序(非稳定)

• 原理解释

速记：就是最左边挖个坑出来part = nums[low]，然后在从右边开始，找一个小于part的数填到左边的坑，这样右边又空出了一个坑，我们按照同样的原理，从左边开始寻找一个大于part的数，填入右边这个坑。

int* sortArray(int* nums, int numsSize, int* returnSize)
{
    if( numsSize < 2 ){
        *returnSize = numsSize;
        return nums;
    }
    int low  = 0;
    int high = numsSize - 1;
    int part = nums[low];       // 左边位置空出来

    while( low < high )
    {
        while( part <= nums[high] && high != low )
            high--;
        nums[low] = nums[high]; // 填入左边位置，右边位置空出来

        while( nums[low] < part && low != high )
            low++;
        nums[high] = nums[low]; // 填入右边位置，左边位置空出来
    }
    nums[low] = part; // 当 low = high 时，循环结束，填入 part 作为分割数

    sortArray( nums, low, returnSize );
    sortArray( &nums[low+1], numsSize - ( low + 1), returnSize );

    *returnSize = numsSize;
    return nums;
}

查找数组第 K 大元素

int findKthLargest(int* nums, int numsSize, int k)
{
    int low  = 0;
    int high = numsSize - 1;
    int assume_k = nums[low];

    while( low < high )
    {
        while( nums[high] < assume_k && low < high )
            high--;
        nums[low] = nums[high];
        while( nums[low] >= assume_k && low < high )
            low++;
        nums[high] = nums[low];
    }

    if( k - 1 == low )
        return assume_k;
    if( k - 1 < low )
        return findKthLargest( nums, low, k );
    else
        return findKthLargest( &nums[low + 1], numsSize - (low + 1), k - (low + 1) );
}

归并排序

非原地排序，空间复杂度O(n)

void merge_sort(int a[], int first, int last)
{
    if( first < last )
    {
        int mid = (first + last) / 2;

        merge_sort(a, first, mid);
        merge_sort(a, mid + 1, last);

        int temp[last-first+1]; // 临时数组(c的可变长数组特性)

        int left  = first;
        int right = mid + 1;
        int k = 0;

        while(left <= mid && right <= last)
        {
            if( a[left] < a[right] )
                temp[k++] = a[left++];
            else
                temp[k++] = a[right++];
        }

        while(left <= mid)
            temp[k++] = a[left++];

        while(right <= last)
            temp[k++] = a[right++];

        for(int i = first, k = 0; i <= last; i++, k++)
            a[i] = temp[k];
    }
}

int* sortArray(int* nums, int numsSize, int* returnSize)
{
    if ( numsSize > 1 )
    {
        int lnumsSzie = 0;
        int *lnums = sortArray( nums, numsSize / 2, &lnumsSzie );

        int rnumsSzie = 0;
        int *rnums = sortArray( &nums[numsSize/2], numsSize - numsSize / 2, &rnumsSzie );

        int *tmpnums = malloc( numsSize * sizeof(int) );
        int i = 0, j = 0, k = 0;
        while( i < lnumsSzie && j < rnumsSzie )
        {
            if( lnums[i] <= rnums[j] )  // 当值相同时，优先放左边数组，就可以保证 稳定性
                tmpnums[k++] = lnums[i++];
            else
                tmpnums[k++] = rnums[j++];
        }
        while( j == rnumsSzie && i < lnumsSzie )
            tmpnums[k++] = lnums[i++];
        while( i == lnumsSzie && j < rnumsSzie )
            tmpnums[k++] = rnums[j++];

        k = 0;
        while( k < numsSize )
            nums[k] = tmpnums[k++];
        free(tmpnums);
    }
    *returnSize = numsSize;
    return nums;
}

桶排序

桶排序假设输入元素均匀而独立分布在区间[0,1) 即 0 <= x and x < 1;将区间划分成n个相同大小的子区间(桶)，然后将n个输入按大小分布到各个桶中去，对每个桶内部进行排序。最后将所有桶的排序结果合并起来

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

/*
 * 参数说明：
 *     a -- 待排序数组
 *     n -- 数组a的长度
 *     max -- 数组a中最大值的范围
 */
void bucketSort(int a[], int n, int max)
{
    int i,j;
    int buckets[max];

    // 将buckets中的所有数据都初始化为0。
    memset(buckets, 0, max*sizeof(int));

    // 1. 计数
    for(i = 0; i < n; i++)
        buckets[a[i]]++;

    // 2. 排序
    for (i = 0, j = 0; i < max; i++)
    {
        while( (buckets[i]--) >0 )
            a[j++] = i;
    }
}

int main( int argc, char *argv[] )
{
    int a[] = {19,33,4,32,33,42,22,44,54,43,32,211,11,34,32};
    bucketSort( a, sizeof(a) / sizeof(int), 211 );
    for( int i = 0; i < sizeof(a) / sizeof(int); i++ )
        printf("%d ",a[i]);
    return 0;
}

计数排序

基数排序