C 语言排序算法

C语言排序算法是一个非常重要的知识点,为什么这么说呢?

很多搜索引擎、索引的应用都是或多或少的居于这些算法演变而来,也就是说它是一个基础,为大型项目开发奠定了一个基础!

当然,学习这些算法,有助于我们对于算法的理解,对于日后的工作也是有很大的帮助的!

算法种类:

  • 冒泡排序
  • 选择排序
  • 插入排序
  • 希尔排序
  • 归并排序
  • 快速排序
  • 基数排序
  • 堆排序

排序分类:

  • 非线性时间比较类排序
    • 交换排序
      • 冒泡排序
      • 快速排序
    • 插入排序
      • 直接插入排序
      • 希尔排序
    • 选择排序
      • 选择排序
      • 堆排序
    • 归并排序
      • 二路归并排序
      • 多路归并排序
  • 线性时间非比较类排序
    • 基数排序
    • 计数排序
    • 桶排序

排序算法总结: sort.png

C语言 冒泡排序

排序思想

  • 比较相邻的两个数,如果前者比后者大,则进行交换。
  • 每一轮排序结束,选出一个未排序中最大的数放到数组后面。
#include <stdio.h>
#include <stdlib.h>

// 冒泡排序
void bubbleSort(int len, int array[])
{
    for(int i = 0; i < len; i ++)
    {
        for(int j = i + 1; j < len; j ++)
        {
            if(array[i] > array[j])
            {
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
    }
}

void myPrintf(int len, int array[])
{
    for(int i = 0; i < len; i ++)
    {
        printf("%d ", array[i]);
    }
}

int main()
{
    int arr[] = {5, 1, 4, 3, 2};
    int len = (int) sizeof(arr) / sizeof(*arr);

    bubbleSort(len, arr);
    myPrintf(len, arr);

    return 0;
}

快速排序

排序思想

  • 选取一个基准元素,通常为数组最后一个元素(或者第一个元素)。
  • 从前向后遍历数组,当遇到小于基准元素的元素时,把它和左边第一个大于基准元素的元素进行交换。
  • 在利用分治策略从已经分好的两组中分别进行以上步骤,直到排序完成。

示例如下:

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

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

//分治法把数组分成两份
int quickSortForPatition(int *a, int left,int right) {
    int j = left;    //用来遍历数组
    int i = j - 1;    //用来指向小于基准元素的位置
    int key = a[right];    //基准元素
    //从左到右遍历数组,把小于等于基准元素的放到左边,大于基准元素的放到右边
    for (; j < right; ++j) {
        if (a[j] <= key)
            swap(&a[j], &a[++i]);
    }
    //把基准元素放到中间
    swap(&a[right], &a[++i]);
    //返回数组中间位置
    return i;
}
//快速排序
void quickSort(int *a,int left,int right) {
    if (left>=right)
        return;
    int mid = quickSortForPatition(a,left,right);
    quickSort(a, left, mid - 1);
    quickSort(a, mid + 1, right);
}

void myPrintf(int len, int array[])
{
    for(int i = 0; i < len; i ++)
    {
        printf("%d ", array[i]);
    }
}

int main()
{
    int arr[] = {5, 1, 4, 3, 2};
    int len = (int) sizeof(arr) / sizeof(*arr);

    //bubbleSort(len, arr);
    quickSort(arr, 0, len - 1);
    myPrintf(len, arr);

    return 0;
}

插入排序

核心思想

  • 和交换排序不同的是它不用进行交换操作,而是用一个临时变量存储当前值。
  • 当前面的元素比后面大时,先把后面的元素存入临时变量,前面元素的值放到后面元素位置,再到最后把其值插入到合适的数组位置。
#include <stdio.h>
#include <stdlib.h>

// 插入排序
void insertSort(int  *a, int n) {
    int tmp = 0;
    for (int i = 1; i < n; i++) {
        int j = i - 1;
        if (a[i] < a[j]) {
            tmp = a[i];
            a[i] = a[j];
            while (tmp < a[j-1]) {
                a[j] = a[j-1];
                j--;
            }
            a[j] = tmp;
        }
    }
}

void myPrintf(int len, int array[])
{
    for(int i = 0; i < len; i ++)
    {
        printf("%d ", array[i]);
    }
}

int main()
{
    int arr[] = {5, 1, 4, 3, 2};

    int len = (int) sizeof(arr) / sizeof(*arr);

    //bubbleSort(len, arr);
    //quickSort(arr, 0, len - 1);
    insertSort(arr, len);
    myPrintf(len, arr);

    return 0;
}

插入排序

核心思想

  • 直接插入排序的思想下设置一个最小增量dk,刚开始dk设置为n/2。
  • 进行插入排序,随后再让dk=dk/2,再进行插入排序,直到dk为1时完成最后一次插入排序,此时数组完成排序。
#include <stdio.h>
#include <stdlib.h>

void shellSort(int *a, int n) {
    int dk = n / 2;        //    设置初始dk
    while (dk >= 1) {
        //Insrtsort(a, n, dk);

        int tmp = 0;
        for (int i = 1; i < n; i++) {
            int j = i - 1;
            if (a[i] < a[j]) {
                tmp = a[i];
                a[i] = a[j];
                while (tmp < a[j-1]) {
                    a[j] = a[j-1];
                    j--;
                }
                a[j] = tmp;
            }
        }

        dk /= 2;
    }
}

void myPrintf(int len, int array[])
{
    for(int i = 0; i < len; i ++)
    {
        printf("%d ", array[i]);
    }
}


int main()
{
    int arr[] = {5, 1, 4, 3, 2};

    int len = (int) sizeof(arr) / sizeof(*arr);

    //bubbleSort(len, arr);
    //quickSort(arr, 0, len - 1);
    //insertSort(arr, len);
    shellSort(arr, len);
    myPrintf(len, arr);

    return 0;
}

选择排序

核心思想

  • 依次选出数组最小的数放到数组的前面。
  • 首先从数组的第二个元素开始往后遍历,找出最小的数放到第一个位置。
  • 再从剩下数组中找出最小的数放到第二个位置。以此类推,直到数组有序。
#include <stdio.h>
#include <stdlib.h>

void selectSort(int *a, int n) {
    for (int i = 0; i < n; i++)
    {
        int key = i;    //    临时变量用于存放数组最小值的位置
        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[key]) {
                key = j;    //    记录数组最小值位置
            }
        }
            if (key != i)
            {
                int tmp = a[key]; a[key] = a[i]; a[i] = tmp;    //    交换最小值
            }

    }
}

void myPrintf(int len, int array[])
{
    for(int i = 0; i < len; i ++)
    {
        printf("%d ", array[i]);
    }
}


int main()
{
    int arr[] = {5, 1, 4, 3, 2};

    int len = (int) sizeof(arr) / sizeof(*arr);

    //bubbleSort(len, arr);
    //quickSort(arr, 0, len - 1);
    //insertSort(arr, len);
    selectSort(arr, len);
    myPrintf(len, arr);

    return 0;
}

堆排序

核心思想

  • 先把数组构造成一个大顶堆(父亲节点大于其子节点),然后把堆顶(数组最大值,数组第一个元素)和数组最后一个元素交换,这样就把最大值放到了数组最后边。
  • 把数组长度n-1,再进行构造堆,把剩余的第二大值放到堆顶,输出堆顶(放到剩余未排序数组最后面)。
  • 依次类推,直至数组排序完成。
#include <stdio.h>
#include <stdlib.h>

void adjuctHeap(int i, int *arr, int count) {
    int tmp;
    int max;

    while(i <= count / 2 - 1) {                 // 条件判断检测是否到了叶子节点
        tmp = 2 * i + 2 >= count ? 0 : arr[2 * i + 2];               //总数为偶数,最后一个父节点没有右孩子
        max = arr[2 * i + 1] >= tmp ? 2 * i + 1 : 2 * i + 2;         //max值:左右孩子中更大的那个孩子节点的下标
        if(arr[max] > arr[i]) {
            tmp = arr[max];
            arr[max] = arr[i];
            arr[i] = tmp;
            i = max;
        }
        else
            break;
    }
}

void heapSort(int *arr, int count) {
    int i;
    int tmp;

    for(i = count / 2 - 1; i > 0; i--) {               // 停留在构造成功大根堆的前一步。 count / 2 - 1 表示倒数第一个非叶子节点。
        adjuctHeap(i, arr, count);
    }

    while(count > 1) {
        adjuctHeap(0, arr, count);                     // 构造大根堆
        tmp = arr[0];
        arr[0] = arr[count - 1];                       // 交换
        arr[count - 1] = tmp;
        --count;                                       // 末尾往前移动
    }
}

void myPrintf(int len, int array[])
{
    for(int i = 0; i < len; i ++)
    {
        printf("%d ", array[i]);
    }
}


int main()
{
    int arr[] = {5, 1, 4, 3, 2};

    int len = (int) sizeof(arr) / sizeof(*arr);

    //bubbleSort(len, arr);
    //quickSort(arr, 0, len - 1);
    //insertSort(arr, len);
    heapSort(arr, len);
    myPrintf(len, arr);

    return 0;
}

归并排序

核心思想

  • 归并算法应用到分治策略,简单说就是把一个答问题分解成易于解决的小问题后一个个解决,最后在把小问题的一步步合并成总问题的解。
  • 这里的排序应用递归来把数组分解成一个个小数组,直到小数组的数位有序,在把有序的小数组两两合并而成有序的大数组。
/*
函数功能:合并
函数参数:
 arr: 目标数组
 start: 待合并段开始下标
 mid: 待合并段中间下标
 end: 待合并段结束下标
 */
void merge(int* arr, int start, int mid, int end)
{
    int len_l, len_r; //左右待合并区间的长度
    len_l = mid - start + 1;
    len_r = end - mid;
    int l[len_l], r[len_r]; //gcc, 两个临时数组,分别保存待合并的两个区间
    //int l[100], r[100]; //vc
    memcpy(l, arr + start, sizeof(int) * len_l);
    memcpy(r, arr + mid + 1, sizeof(int) * len_r);

    int i = 0, j = 0, k = start;
    while(i < len_l && j < len_r)
    {
        arr[k++] = l[i] < r[j] ? l[i++] : r[j++];
    }

    while(i < len_l)
    {
        arr[k++] = l[i++];
    }
}
/*
函数功能:归并排序
函数参数:
 arr: 待排序的数组
 start: 待排序数组开始下标
 end: 待排序数组结束下标
 */
void mergeSort(int* arr, int start, int end)
{
    if(start < end)
    {
        int mid = (start + end) / 2;
        //归
        mergeSort(arr, start, mid);
        mergeSort(arr, mid + 1, end);
        //并
        merge(arr, start, mid, end);
    }
}

void myPrintf(int len, int array[])
{
    for(int i = 0; i < len; i ++)
    {
        printf("%d ", array[i]);
    }
}

int main()
{
    int arr[] = {5, 1, 4, 3, 2};

    int len = (int) sizeof(arr) / sizeof(*arr);

    //bubbleSort(len, arr);
    //quickSort(arr, 0, len - 1);
    //insertSort(arr, len);
    mergeSort(arr, 0, len - 1);
    myPrintf(len, arr);

    return 0;
}