嵌入式方向要掌握的最简单的排序算法，先不说动态规划等其他算法，简单的也要会手撕。

本文不讲原理，只谈代码。

直接插入排序

 1void Insert_Sort(int* array, int size) {
 2    for (int i = 1; i < size; i++) {
 3        int temp = array[i];
 4        int j    = i - 1;
 5        while (j >= 0 && array[j] > temp) {
 6            array[j + 1] = array[j];
 7            j--;
 8        }
 9        array[j + 1] = temp;
10    }
11}

希尔排序

 1void shell_sort(int *array,int size){
 2    int interval = size >> 1;
 3    while(interval){
 4        for(int i = interval; i < size; i++) {
 5            int temp = array[i];
 6            int j = i;
 7            while(array[j - interval] > temp && j - interval >= 0) {
 8                array[j] = array[j - interval];
 9                j -= interval;
10            }
11            array[j] = temp;
12        }
13        interval >>= 1;
14    }
15}

直接选择排序

 1void swap(int *array,int i,int j){
 2    array[i] = array[i] + array[j];
 3    array[j] = array[i] - array[j];
 4    array[i] = array[i] - array[j];
 5}
 6void select_sort(int *array,int size){
 7    for(int i = 0 ; i < size - 1 ; ++i){
 8        int k = i ;
 9        for(int j = i + 1 ; j < size ; ++j){
10            if(array[j]<array[k]) k=j;
11        }
12        swap(array,k,i);
13    }
14}

冒泡排序

1void bubble_sort(int *array,int size){
2    for(int i = 0 ; i < size - 1 ; ++i){
3        for(int j = 0; j < size - 1 - i ; ++j){
4            if(array[j] > array[j+1])swap(array,j,j+1);
5        }
6    }
7}

快速排序

 1int paritition(int A[],int left,int right){
 2    int mid = A[left];
 3    while(left < right){
 4        while(left < right && A[right] >= mid)right--;
 5        A[left] = A[right];
 6        while(left < right && A[left] <= mid)left++;
 7        A[right] = A[left];
 8    }
 9    A[left] = mid;
10    return left;
11}
12void quickSort(int A[],int left,int right){
13    if(left < right){
14        int mid = paritition(A,left,right);
15        quickSort(A,left,mid-1);
16        quickSort(A,mid+1,right);
17    }
18}

归并排序

 1void merge(int *list,int left,int mid,int right)
 2{
 3    int i = left,j = mid+1;
 4    int k = 0;
 5    int temp[right-left];
 6    while (i <= mid && j <= right)
 7    {
 8        if(list[i] < list[j])
 9            temp[k++] = list[i++];
10        else
11            temp[k++] = list[j++];
12    }//当比较晚之后某数组还有剩余元素
13    while(i <= mid)temp[k++] = list[i++];
14    while(j <= right)temp[k++] = list[j++];
15    for(i = 0;i < k;i++)list[left+i] = temp[i];
16}
17int* merge_sort(int *list,int left,int right)
18{
19    if(left < right)
20    {
21        int mid = (left + right) >> 1;
22        merge_sort(list,left,mid);
23        merge_sort(list,mid+1,right);
24        merge(list,left,mid,right);
25    }
26    return list;
27}

    

公众号'艾恩凝' 个人微信

    吾心信其可行，
          则移山填海之难，
                  终有成功之日！
                                  ——孙文