插入,希尔,快速,归并 四大排序实现

文章链接:https://codemouse.online/archives/2020-05-17-22-08-18

插入排序

// 插入排序,从大到小
void sortInsert(int* arr, int len)
{
    int temp = 0;

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

希尔排序

// 希尔排序(插入排序直接改进,加入一个步长机制)
void sortShell(int* arr, int len)
{
    
    int temp = 0;
    // k为步长
    for(int k = len/2; k>0; k/=2)
    {
        for ( int i = k,j =0; i < len ; i+=k)
        {
            temp = arr[i];
            for (j = i-k; j >= 0 && arr[j] < temp; j-=k)
            {
               arr[j+k] = arr[j];
            }
            arr[j+k] = temp;
        }

    }
}

快速排序

void quick(int *arr,int start, int end)
{
    if(start>=end) return;
    // 设置基准key
    int key = arr[start];
    int l = start;
    int h = end;
    while(l<h)
    {

        while(l<h && key >= arr[h])
            h--;
        arr[l] = arr[h];
        while(l<h && key <= arr[l])
            l++;
        arr[h] = arr[l];
    }
    arr[l] = key;
    // 分割数组(逻辑上)
    quick(arr,start,l-1);
    quick(arr,l+1,end);
}
// 快速排序
void sortQuick(int *arr, int len)
{
    quick(arr,0,len-1);
}

归并排序

void merge(int *arr, int *temp, int begin, int mid, int end)
{
    int left = begin; 
    int right = mid+1;
    int len = end - begin + 1;
    for(int i = 0; i < len ; i++)
    {
        if(left > mid){ // 左边已经全部取完
            temp[i] = arr[right++];
        }else if(right > end){ // 右边已经全部取完
            temp[i] = arr[left++];
        }else if(arr[left] < arr[right]){ // 从大到小排序
            temp[i] = arr[right++];
        }else{
            temp[i] = arr[left++];
        }
    }
    // 将辅助数组的数据写回
    memcpy(arr+begin,temp, sizeof(int)*len);
}

void splitMerge(int *arr,int *temp, int begin, int end)
{
    if(begin>=end) return;
    int mid = (begin+end)/2;
    // 拆分数组
    splitMerge(arr,temp, begin,mid);
    splitMerge(arr,temp, mid+1,end);
    // 合并数组
    merge(arr, temp, begin,mid, end);

}
// 归并排序
void sortMerge(int *arr, int len)
{
    // 归并排序是一个外排序,需要数组辅助
    int *temp = (int *)malloc(sizeof(int)*len);
    splitMerge(arr,temp,0,len-1);
    free(temp);
}

实例演示

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

void main()
{
    int arr[ARRNUM]={234,52,123,5,346,32,5345,6345,131,35};
    int arr1[ARRNUM];
    int arr2[ARRNUM];
    int arr3[ARRNUM];

    memcpy(arr1,arr,ARRNUM*sizeof(int));
    memcpy(arr2,arr,ARRNUM*sizeof(int));
    memcpy(arr3,arr,ARRNUM*sizeof(int));

    
    sortInsert(arr, ARRNUM);
    printArr(arr, ARRNUM);

    sortShell(arr1, ARRNUM);
    printArr(arr1, ARRNUM);
        
    sortQuick(arr2, ARRNUM);
    printArr(arr2, ARRNUM);

    sortMerge(arr3, ARRNUM);
    printArr(arr3, ARRNUM);

}