冒泡排序

相邻的两个数据进行比较，小的数放到前面，大的放到后面。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// 冒泡法
void bubSort(int arr[], int arrLen)
{
    while(arrLen--)
    {
        for (int i = 0; i < arrLen; i++)
        {
            if (arr[i] > arr[i+1])
            {
                int temp = arr[i];
                arr[i] = arr[i+1];
                arr[i+1] = temp;
            }
        }
    }
}

// 优化，当已经是顺序时无需再排序
void bubSortPro(int arr[], int arrLen)
{
    int flag = 1;
    while(arrLen-- && flag)
    {
        flag = 0;
        for (int i = 0; i < arrLen; i++)
        {
            if (arr[i] > arr[i+1])
            {
                flag = 1;
                int temp = arr[i];
                arr[i] = arr[i+1];
                arr[i+1] = temp;
            }
        }
    }
}

选择排序

找到每轮的最小值，然后再放到当前轮的首位置，不用像冒泡法一样每次都得交换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void selectSort(int arr[], int arrLen)
{
    for (int i = 0; i < arrLen; i++)
    {
        int k = i;
        for (int j = (i + 1); j < arrLen; j++)
        {
            if (arr[k] > arr[j])
            {
                k = j;  // k 用于记录每轮最小值的位置
            }
        }

        if (i != k)
        {
            int temp = arr[i];
            arr[i] = arr[k];
            arr[k] = temp;
        }
    }
}

插入排序

插入排序适用于已经基本有序的序列。

依次将数据插入前面已经排号序的序列中。

1
2
3
4
5
6
7
8
9
10
11
12
13
void insertSort(int arr[], int arrLen)
{
    int i, j, temp;
    for (i = 1; i < arrLen; i++)
    {
        temp = arr[i];  // 要插入的数据
        for (j = i; (j >= 1) && (arr[j-1] > temp); j--)   // 大于 temp 的元素向后移动一位
        {
            arr[j] = arr[j-1];
        }
        arr[j] = temp;
    }
}

希尔排序

希尔排序（Shell Sort）是插入排序的一种改进版本，也称为递减增量排序算法。它通过比较距离较远的元素来进行排序，逐步减少间隔，直到间隔为1时进行一次普通的插入排序。这样可以在数据部分有序的情况下，显著提高排序效率。

希尔排序适用于大量数据情况下的排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 基于希尔序列的希尔排序
void shellSort(int arr[], int arrLen)
{
    int i, j, temp;
    int h = arrLen / 2;		// 首次步长先设置为一半

    while (h >= 1)
    {
        // 做步长为 h 的插入排序
        for (i = h; i < arrLen; i++)
        {
            temp = arr[i];  // 要插入的数据
            for (j = i; (j >= h) && (arr[j-h] > temp); j -= h)   // 大于 temp 的元素向后移动一位
            {
                arr[j] = arr[j-h];
            }
            arr[j] = temp;
        }
        h /= 2;
    }
}

希尔排序的性能依赖于间隔序列的选择，常用的间隔序列有希尔序列（初始间隔为数组长度的一半，每次减半）和希伯特序列（基于质数或素数序列的间隔）。不同的间隔序列可能对不同的数据集有不同的效果。

快速排序

快速排序（Quick Sort）是一种高效的排序算法，它采用分治法的策略来把一个序列分为较小和较大的两个子序列，然后递归地排序两个子序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// 交换两个元素的值  
void swap(int *a, int *b) 
{  
    int temp = *a;  
    *a = *b;  
    *b = temp;  
}  

// 分区函数，选择基准点并重新排列数组  
int partition(int arr[], int low, int high) 
{
    int pivot = arr[high];   // 最右边当轴并记录轴值
    int i = low;
    for (int j = low; j < high; j++)
    {
        // 所有比轴小的值全都交换到左边
        if (arr[j] <= pivot)
        {
            swap(&arr[i], &arr[j]);
            i++;
        }
    }
    swap(&arr[i], &arr[high]);
    return i;
}

// 快速排序函数  
void quickSort(int arr[], int low, int high) 
{  
    int pivot;
    if (low < high)
    {
        pivot = partition(arr, low, high);
        quickSort(arr, low, pivot - 1);
        quickSort(arr, pivot + 1, high);
    }
}

归并排序

归并排序是一种有效的、稳定的、基于比较的排序算法，它采用分治法将一个列表分成较小的子列表，递归地排序每个子列表，然后将已排序的子列表合并成一个最终的排序列表。

先假设有两个有序的数组，现在将其合并并排序，代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
void mergeSort(int *arr1, int len1, int *arr2, int len2, int *temp)
{
    int i = 0;
    int j = 0;
    int k = 0;
    while (i < len1 && j < len2)
    {
        if (arr1[i] < arr2[j])
        {
            temp[k] = arr1[i];
            i++;
            k++;
        }
        else
        {
            temp[k] = arr2[j];
            j++;
            k++;
        }
    }
    
    // 剩下的数据直接拷贝到temp数组后即可
    while (i < len1)
    {
        temp[k] = arr1[i];
        i++;
        k++;
    }
    while (j < len2)
    {
        temp[k] = arr2[j];
        j++;
        k++;
    }
}

简化后

1
2
3
4
5
6
7
8
9
10
void mergeSort(int *arr1, int len1, int *arr2, int len2, int *temp)
{
    int i = 0, j = 0, k = 0;
    while (i < len1 && j < len2)
        temp[k++] = arr1[i] < arr2[j] ? arr1[i++] : arr2[j++];
    while (i < len1)
        temp[k++] = arr1[i++];
    while (j < len2)
        temp[k++] = arr2[j++];
}

基于此思想实现真正的归并排序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
void merge(int arr[], int low, int mid, int height, int temp[])
{
    int i = low;
    int j = mid + 1;
    int k = low;

    while (i <= mid && j <= height)
        temp[k++] = arr[i] < arr[j] ? arr[i++] : arr[j++];
    while (i <= mid)
        temp[k++] = arr[i++];
    while (j <= height)
        temp[k++] = arr[j++];

    for (i = low; i <= height; i++)
        arr[i] = temp[i];
}

void merge_Sort(int arr[], int low, int height, int temp[])
{
    if (low >= height)
        return;
    int mid = low + ((height - low) / 2);
    merge_Sort(arr, low, mid, temp);
    merge_Sort(arr, mid + 1, height, temp);
    merge(arr, low, mid, height, temp);
}

void mergeSort(int *arr, int len)
{
    int *temp = (int *)malloc(sizeof(int) * len);
    if (temp == NULL)
    {
        printf("malloc fail\n");
    }
    merge_Sort(arr, 0, len - 1, temp);
    free(temp);
}

堆排序

计数排序

计数排序是一种非比较的排序算法，适用于整数数组，特别是当整数的范围不是很大时。计数排序的基本思想是统计每个元素的出现次数，然后根据这些次数来重新排列数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <assert.h>
#include <string.h>

#define DATA_MAX        100

void countSort(int *arr, int len)
{
    int i, j;
    int *temp = (int *)malloc(DATA_MAX * sizeof(int));
    memset(temp, 0, DATA_MAX * sizeof(int)); // 清零
    
    for (i = 0; i < len; i++)
        temp[arr[i]]++;
    for (j = 0, i = 0; j < DATA_MAX; j++)
        while (temp[j]--)
            arr[i++] = j;
}

基数排序

桶排序的思想，按照数字的位数进行排序，准备0-9的链式队列，从低位开始到高位进行排序，当最高位被排好序后原来的序列自然排好序了。
例如：对以下序列进行基数排序
578，234，86，432，512，618，384
排序过程：
第一轮（在第零轮的基础上按位排在第零轮的基础上按位排在第零轮的基础上按100位排）：432，512，234，384，86，578，618
第二轮（在第一轮的基础上按位排在第一轮的基础上按位排在第一轮的基础上按101位排）：512，618，432，234，578，384，86
第三轮（在第二轮的基础上按位排在第二轮的基础上按位排在第二轮的基础上按102位排）：86，234，384，432，512，578，618

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
void redixSort(int *arr, int len)
{
    int i, j, k, index;
    int temp[10][ARR_MAX_LEN];

    for (i = 0; i < 10; i++)
        for (j = 0; j < ARR_MAX_LEN; j++)
            temp[i][j] = -1;
    
    // 依次进行个位、十位、百位的排序
    for (k = 10; k <= 1000; k *= 10)
    {
        // 遍历数组，依次存放于对应的“桶”中
        for (i = 0; i < ARR_MAX_LEN; i++)
        {
            j = 0;
            index = ((arr[i] % k) / (k / 10));
            while (temp[index][j] != -1)
            {
                j++;
            }
            temp[index][j] = arr[i];
        }

        // 依次从桶中取出数据重新放回数组，这样就完成了这一轮的排序
        for (i = 0, index = 0; i < 10; i++)
        {
            j = 0;
            while (temp[i][j] != -1)
            {
                arr[index++] = temp[i][j];
                temp[i][j] = -1;    // 为了下一个循环遍历
                j++;
            }
        }
    }
}

桶排序