C语言排序算法的讲解

一、常用排序算法

选择排序

选择排序是一种简单直观的排序算法。

它的工作原理如下：

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。 以此类推，直到所有元素均排序完毕。

插入排序

插入排序也是一种简单直观的排序算法。

它的工作原理如下：

是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

快速排序

快速排序使用分治法策略来把一个序列分为两个子序列。（其实就是找个元素把整体一分为二）

除了用我下面的代码实现之外，也可以用C语言提供的qsort函数进行快排。

步骤为：

1. 从数列中挑出一个元素，书上称为“基准”。
2. 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分割结束之后，该基准就处于数列的中间位置。这个称为分割操作。
3. 递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。
4. 递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代中，它至少会把一个元素摆到它最后的位置去。

代码演示

    #include<stdio.h>
    #define N 8 //方便修改数组长度

    /*
        项目介绍：演示排序算法的实现过程
        作者：连思鑫
        时间：2021-12-10
    */

    //自定义的输出函数
    void print(int a[], int n, int i) {
        printf("%d:", i);
        for (int j = 0; j < n; j++) {
            printf("%d ", a[j]);
        }
        printf("\n");
    }
    //直接插入排序函数
    void InsertSort(int a[], int n)
    {
        for (int i = 1; i < n; i++) {
            if (a[i] < a[i - 1]) {//若第 i 个元素大于 i-1 元素则直接插入；反之，需要找到适当的插入位置后在插入。
                int j = i - 1;
                int x = a[i];
                while (j > -1 && x < a[j]) {  //采用顺序查找方式找到插入的位置，在查找的同时，将数组中的元素进行后移操作，给插入元素腾出空间
                    a[j + 1] = a[j];
                    j--;
                }
                a[j + 1] = x;      //插入到正确位置
            }
            print(a, n, i);//打印每次排序后的结果
        }
    }

    //选择排序
    void selection_sort(int a[], int n)
    {
        int i, j, temp;

        for (i = 1; i < n - 1; i++)
        {
            int min = i;                  // 记录最小值，第一个元素默认最小
            for (j = i + 1; j < n; j++)     // 访问未排序的元素
            {
                if (a[j] < a[min])    // 找到目前最小值
                {
                    min = j;    // 记录最小值
                }
            }
            if (min != i)
            {
                temp = a[min];  // 交换两个变量
                a[min] = a[i];
                a[i] = temp;
            }
            print(a, n, i);
        }
    }

    //快速排序
    //迭代法
    typedef struct _Range {
        int start, end;
    } Range;
    Range new_Range(int s, int e) {
        Range r;
        r.start = s;
        r.end = e;
        return r;
    }
    void swap(int* x, int* y) {
        int t = *x;
        *x = *y;
        *y = t;
    }
    void quick_sort(int arr[], const int len) {
        if (len <= 0)
            return; // 避免len等於負值時引發段錯誤（Segment Fault）
        // r[]模擬列表,p為數量,r[p++]為push,r[--p]為pop且取得元素
        Range r[N];
        int p = 0;
        r[p++] = new_Range(0, len - 1);
        while (p) {
            Range range = r[--p];
            if (range.start >= range.end)
                continue;
            int mid = arr[(range.start + range.end) / 2]; // 選取中間點為基準點
            int left = range.start, right = range.end;
            do
            {
                while (arr[left] < mid) ++left;   // 檢測基準點左側是否符合要求
                while (arr[right] > mid) --right; //檢測基準點右側是否符合要求

                if (left <= right)
                {
                    swap(&arr[left], &arr[right]);
                    left++; right--;               // 移動指針以繼續
                }
            } while (left <= right);

            if (range.start < right) r[p++] = new_Range(range.start, right);
            if (range.end > left) r[p++] = new_Range(left, range.end);
            print(arr, len, r);
        }
    }

    //递归法
    void quick_sort_recursive(int arr[], int start, int end) {
        if (start >= end)
            return;
        int mid = arr[end];
        int left = start, right = end - 1;
        while (left < right) {
            while (arr[left] < mid && left < right)
                left++;
            while (arr[right] >= mid && left < right)
                right--;
            swap(&arr[left], &arr[right]);
        }
        if (arr[left] >= arr[end])
            swap(&arr[left], &arr[end]);
        else
            left++;
        if (left)
            quick_sort_recursive(arr, start, left - 1);
        quick_sort_recursive(arr, left + 1, end);
    }
    void quick_sort2(int arr[], int len) {
        quick_sort_recursive(arr, 0, len - 1);
    }

    int main() {
        int a[N] = { 14,33,27,10,35,19,42,44 };
        InsertSort(a, N);
        //selection_sort(a, N);
        //quick_sort(a, N);
        //quick_sort2(a, N);
        return 0;
    }