简单排序算法

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

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

直接插入排序

void Insert_Sort(int* array, int size) {
    for (int i = 1; i < size; i++) {
        int temp = array[i];
        int j    = i - 1;
        while (j >= 0 && array[j] > temp) {
            array[j + 1] = array[j];
            j--;
        }
        array[j + 1] = temp;
    }
}

希尔排序

void shell_sort(int *array,int size){
    int interval = size >> 1;
    while(interval){
        for(int i = interval; i < size; i++) {
            int temp = array[i];
            int j = i;
            while(array[j - interval] > temp && j - interval >= 0) {
                array[j] = array[j - interval];
                j -= interval;
            }
            array[j] = temp;
        }
        interval >>= 1;
    }
}

直接选择排序

void swap(int *array,int i,int j){
    array[i] = array[i] + array[j];
    array[j] = array[i] - array[j];
    array[i] = array[i] - array[j];
}
void select_sort(int *array,int size){
    for(int i = 0 ; i < size - 1 ; ++i){
        int k = i ;
        for(int j = i + 1 ; j < size ; ++j){
            if(array[j]<array[k]) k=j;
        }
        swap(array,k,i);
    }
}

冒泡排序

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

快速排序

int paritition(int A[],int left,int right){
    int mid = A[left];
    while(left < right){
        while(left < right && A[right] >= mid)right--;
        A[left] = A[right];
        while(left < right && A[left] <= mid)left++;
        A[right] = A[left];
    }
    A[left] = mid;
    return left;
}
void quickSort(int A[],int left,int right){
    if(left < right){
        int mid = paritition(A,left,right);
        quickSort(A,left,mid-1);
        quickSort(A,mid+1,right);
    }
}

归并排序

void merge(int *list,int left,int mid,int right)
{
    int i = left,j = mid+1;
    int k = 0;
    int temp[right-left];
    while (i <= mid && j <= right)
    {
        if(list[i] < list[j])
            temp[k++] = list[i++];
        else
            temp[k++] = list[j++];
    }//当比较晚之后某数组还有剩余元素
    while(i <= mid)temp[k++] = list[i++];
    while(j <= right)temp[k++] = list[j++];
    for(i = 0;i < k;i++)list[left+i] = temp[i];
}
int* merge_sort(int *list,int left,int right)
{
    if(left < right)
    {
        int mid = (left + right) >> 1;
        merge_sort(list,left,mid);
        merge_sort(list,mid+1,right);
        merge(list,left,mid,right);
    }
    return list;
}


    


公众号'艾恩凝'
个人公众号
个人微信
个人微信
    吾心信其可行,
          则移山填海之难,
                  终有成功之日!
                                  ——孙文
    评论
    0 评论
avatar

取消