浅谈几个重要的排序算法，实现数组的升序排序

初始代码:

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

#define NUM 10

void travel(int *arr,int len,bool sorted=false);

int main(void)
{
    int arr[NUM] = {1,9,0,5,7,2,12,54,21,33}; // 测试数组

    // 排序函数
    
    travel(arr,NUM,true); // 遍历

    return 0;
}

void travel(int *arr,int len,bool sorted)
{
    for (int i=0;i<len;i++) {
        printf("%d ",arr[i]);
    }
    printf("\n");
}

冒泡排序

比较相邻的元素，如果第一个比第二个大，就交换它们两个，对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这步做完后，最后的元素会是最大的数。针对所有的元素重复以上的步骤，除了最后一个，持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较

void bubble_sort(int *arr,int len)
{
    int temp;
    for (int i=0;i<len-1;i++) {
        for (int j=0;j<len-i-1;j++)
            if (arr[j] > arr[j+1]) {
                temp = arr[j+1];
                arr[j+1] = arr[j];
                arr[j] = temp;
            }
    }
}

选择排序

*每次选择最小的，放到应该放的位置

void select_sort(int *arr,int len)
{
    int index; 
    for (int i=0;i<len-1;i++) {
        index = i;
        for (int j=i;j<len;j++) {
            index = arr[index]<arr[j]? index:j; 
        }
        int temp = arr[i];
        arr[i] = arr[index];
        arr[index] = temp;
    } 
}

如上所示，每次找到第i个元素后面的最小元素，然后和第i个元素交换

插入排序

将待排数组的第一个元素看成是一个有序数组，然后将一个个其他元素插入到这个数组中，从后往前找插入位置

void insert_sort(int *arr,int len)
{ 
    int temp,j;  
    for (int i=1;i<len;i++) {
        temp = arr[i];
        for (j=i-1;j>=0 && arr[j]>temp;j--) {
            arr[j+1] = arr[j]; // 比temp大的元素后移
        }
        // insert
        arr[j+1] = temp;
    }
}

希尔排序

上述3种排序算法效率都比较低，希尔排序的效率相对较高，在插入排序的基础上再做优化，但并非稳定的算法

先分组，在组内做插入排序，这样可以减少移动元素的次数，组的数量称为步长

void shell_sort(int* arr,int len)
{
    int step = len / 2;
    while (step) {
        for (int i=step;i<len;i++) {
            int temp = arr[i],j;
            for (j=i-step;j>=0 && arr[j]>temp;j-=step) {
                arr[j+step] = arr[j];
            }
            arr[j+step] = temp;
        }
        step /= 2;
    }
}

每次循环，步长会逐渐减小

基数排序

不同于上述四种基于比较的排序算法，基数排序不基于比较，效率较高，但有所限制条件

void radix_sort(int *arr,int len,int max)
{
    // 开临时数组
    int *pTemp = new int[max+1];
	
    // 都赋值为-1
    for (int i=0;i<max+1;i++) {
        pTemp[i] = -1;
    }
	
    for (int i=0;i<len;i++) {
        pTemp[arr[i]] = arr[i];
    }

    int k = 0;
    for (int i=0;i<max+1;i++) {
        if (-1 != pTemp[i])
            arr[k++] = pTemp[i];
    }
    delete[] pTemp;
}

可以看到这个算法利用了数组下标天然有序的特点

这个排序方法有着如下限制:

1. 只能是正整数
2. 元素不能重复
3. 特别注意内存空间，如果max相当大，显然对内存空间是一个巨大的浪费

最后

以上列举了5种较为简单的排序算法，后续会再详细介绍复杂一点的算法