苦于记不住八大排序？现成的模板它不香？_未央吖的博客

 -以下都是调用函数-遇到相关排序题直接套用即可

选择排序

void selection_sort(int arr[], int len) 
{
    int i,j;
 
    for (i = 0 ; i < len - 1 ; i++)         //进行len-1趟
    {
        int min = i;                        //设为最小的
        for (j = i + 1; j < len; j++)     
            if (arr[j] < arr[min])    
                min = j;                    //找最小的
                int temp = arr[min];        //交换
                arr[min]= arr[i];
                arr[i] = temp;
               
    }
}

冒泡排序

void bubble_sort(int a[],int n)//n为数组a的元素个数
{
    //一定进行N-1轮比较
    for(int i=0; i<n-1; i++)
    {
        //每一轮比较前n-1-i个，即已排序好的最后i个不用比较
        for(int j=0; j<n-1-i; j++)
        {
            if(a[j] > a[j+1])
            {
                int temp = a[j];
                a[j] = a[j+1];
                a[j+1]=temp;
            }
        }
    }
}

插入排序

void insert_sort(int a[],int n)//n为数组a的元素个数
{
    //进行N-1轮插入过程
    for(int i=1; i<n; i++)
    {
        //首先找到元素a[i]需要插入的位置
        int j=0;
        while( (a[j]<a[i]) && (j<i))
        {
            j++;
        }
        //将元素插入到正确的位置
        if(i != j)  //如果i==j，说明a[i]刚好在正确的位置
        {
            int temp = a[i];
            for(int k = i; k > j; k--)
            {
                a[k] = a[k-1];
            }
            a[j] = temp;
        }
    }
}

 希尔排序

int shsort(int s[], int n)    /* 自定义函数 shsort()*/
{
    int i,j,d;
    d=n/2;    /*确定固定增虽值*/
    while(d>=1)
    {
        for(i=d+1;i<=n;i++)    /*数组下标从d+1开始进行直接插入排序*/
        {
            s[0]=s[i];    /*设置监视哨*/
            j=i-d;    /*确定要进行比较的元素的最右边位置*/
            while((j>0)&&(s[0]<s[j]))
            {
                s[j+d]=s[j];    /*数据右移*/
                j=j-d;    /*向左移d个位置V*/
            }
            s[j + d]=s[0];    /*在确定的位罝插入s[i]*/
        }
        d = d/2;    /*增里变为原来的一半*/
    }
return 0;
}

快速排序

void Swap(int *p, int *q)         //交换函数
{
    int buf;
    buf = *p;
    *p = *q;
    *q = buf;
    return;
}
void QuickSort(int *a, int low, int high)
{
    int i = low;            //最小
    int j = high;           //最大
    int key = a[low];
    if (low >= high)  //如果low >= high说明排序结束了
    {
        return ;
    }
    while (low < high)  //该while循环结束一次表示比较了一轮
    {
        while (low < high && key <= a[high])
        {
            --high;  //向前寻找
        }
        if (key > a[high])
        {
            Swap(&a[low], &a[high]);
            ++low;
        }
        while (low < high && key >= a[low])
        {
            ++low;  //向后寻找
        }
        if (key < a[low])
        {
            Swap(&a[low], &a[high]);
            --high;
        }
    }
    QuickSort(a, i, low-1);  //用同样的方式对分出来的左边的部分进行同上的做法
    QuickSort(a, low+1, j);  //用同样的方式对分出来的右边的部分进行同上的做法
}

基数排序

int getDigitNum(int x){ 
  if(x == 0) return 1; 
  int res = 0; 
  while(x){ 
    res ++; 
    x /= 10; 
  } 
  return res; 
} 
void RadixSort(int data[], int n){ 
  //find the Maximum and its digit number 
  int Max = data[0]; 
  for(int i = 1; i < n; i++){ 
    if(Max < data[i]) Max = data[i]; 
  } 
  int maxNum = getDigitNum(Max); 
  //maxNum times radix sort 
  int divisor = 1; 
  for(int k = 0; k < maxNum; k++){ 
    vector<int> g[10];//g[i]中包含了"末位"数字是i的data[]数组中的元素 
    for(int i = 0; i < 10; i++) g[i].clear(); 
    for(int i = 0; i < n; i++){ 
      int tmp = data[i] / divisor % 10; 
      g[tmp].push_back(data[i]); 
    } 
    int cnt = 0; 
    for(int i = 0; i < 10; i++){ 
      for(int j = 0; j < g[i].size(); j++){ 
        data[cnt++] = g[i][j]; 
      } 
    } 
    divisor *= 10; 
  } 
} 

归并排序

void merges(int arr[], int low, int mid, int high){
    int i, k;
    int *tmp = (int *)malloc((high-low+1)*sizeof(int));
    //申请空间，使其大小为两个
    int left_low = low;
    int left_high = mid;
    int right_low = mid + 1;
    int right_high = high;

    for(k=0; left_low<=left_high && right_low<=right_high; k++){  // 比较两个指针所指向的元素
        if(arr[left_low]<=arr[right_low]){
            tmp[k] = arr[left_low++];
        }else{
            tmp[k] = arr[right_low++];
        }
    }

    if(left_low <= left_high){  //若第一个序列有剩余，直接复制出来粘到合并序列尾
    //memcpy(tmp+k, arr+left_low, (left_high-left_low+l)*sizeof(int));
    for(i=left_low;i<=left_high;i++)
        tmp[k++] = arr[i];
    }

    if(right_low <= right_high){
    //若第二个序列有剩余，直接复制出来粘到合并序列尾
    //memcpy(tmp+k, arr+right_low, (right_high-right_low+1)*sizeof(int));
        for(i=right_low; i<=right_high; i++)
            tmp[k++] = arr[i];
    }

    for(i=0; i<high-low+1; i++)
        arr[low+i] = tmp[i];
    free(tmp);
    return;
}

void merge_sort(int arr[], unsigned int first, unsigned int last){
    int mid = 0;
    if(first<last){
        mid = (first+last)/2; /* 注意防止溢出 */
        /*mid = first/2 + last/2;*/
        //mid = (first & last) + ((first ^ last) >> 1);
        merge_sort(arr, first, mid);
        merge_sort(arr, mid+1,last);
        merges(arr,first,mid,last);
    }
    return;
}

堆排序

void
heapAdjust(int n, int par)
{
    int tmp, pos, lc, rc;

    while (par <= n/2) {
        tmp = h[par]; //记录父母结点键值
        lc = par<<1;
        rc = lc+1;
        pos = par;
        //父母结点至多更新2次
        if (h[par] < h[lc]) {
            h[par] = h[lc];
            pos = lc;
        }
        if (rc <= n && h[par] < h[rc]) {
            h[par] = h[rc];
            pos = rc;
        }
        if (pos == par) //无更新即无需调整
            break;
        else
            h[pos] = tmp;
        par = pos; //假设这个位置的结点是“父母结点”
    }
}

//创建堆
//规模为n的堆，对其父母结点，自底向上自右向左地调整堆
void
createHeap(int n)
{
    int i;

    for (i = n/2; i != 0; i--) {
        heapAdjust(n, i);
    }
}

void
heapSort(int n)
{
    int ntimes = n;

    while (ntimes--) {
        printf("%d\n", h[1]);
        h[1] = h[n];
        h[n--] = 0; //堆清零
        heapAdjust(n, 1);
    }
}

看不懂？不会上面的模板？

友情请来我们的C语言排序的大佬

qsort函数

直接套用这个模板

调用函数

int cmp ( const void *a , const void *b )

{ return *(int *)a - *(int *)b; }        从小到大的排序

int cmp ( const void *a , const void *b )

{ return *(int *)b - *(int *)a; }       从大到小的排序

 放在主函数的内容

qsort(nums,numsSize,sizeof(int),cmp)；

更多详情点击 https://www.cnblogs.com/syxchina/archive/2010/07/29/2197382.html

牛刀小试

注意注意！！力扣困难题来袭

 

没用qsort函数前

int maximumGap(int* nums, int numsSize) {
    if (numsSize < 2) {
        return 0;
    }
    int exp = 1;
    int buf[numsSize];
    memset(buf, 0, sizeof(buf));
    int maxVal = INT_MIN;
    for (int i = 0; i < numsSize; ++i) {
        maxVal = fmax(maxVal, nums[i]);
    }

    while (maxVal >= exp) {
        int cnt[10];
        memset(cnt, 0, sizeof(cnt));
        for (int i = 0; i < numsSize; i++) {
            int digit = (nums[i] / exp) % 10;
            cnt[digit]++;
        }
        for (int i = 1; i < 10; i++) {
            cnt[i] += cnt[i - 1];
        }
        for (int i = numsSize - 1; i >= 0; i--) {
            int digit = (nums[i] / exp) % 10;
            buf[cnt[digit] - 1] = nums[i];
            cnt[digit]--;
        }
        memcpy(nums, buf, sizeof(int) * numsSize);
        exp *= 10;
    }

    int ret = 0;
    for (int i = 1; i < numsSize; i++) {
        ret = fmax(ret, nums[i] - nums[i - 1]);
    }
    return ret;
}

 用了qsort后

 

int cmp(int *a,int *v)
{
    return *a-*v;
}
int maximumGap(int* nums, int numsSize){
qsort(nums,numsSize,sizeof(int),cmp);       //qsort函数排序
int max=0;
if(numsSize<2)return 0;
for(int i=0;i<numsSize-1;i++)
{
  max=fmax(nums[i+1]-nums[i],max);        //fmax  C语言里的一种函数求最大
 
}return max;
}