首页 > 十种经典排序算法精粹(c语言版本)

十种经典排序算法精粹(c语言版本)

下面给出这段时间我苦心研究验证过的十种经典排序算法的C语言版本，即下面的排序算法：

插入排序，shell排序，冒泡排序，快速排序，选择排序，堆排序，归并排序，桶排序，基数排序和计数排序。整理出来以作备忘，不足之处，欢迎大家批评指正！其中计数排序分别给出了不稳定和稳定两种排序算法，测试时，使用随机生成大数组和随机手动输入的方法来测试。

//description: 这里给出了c语言版本的10种排序算法
//refer: 参考自Weiss的教材及网上资料
//compile: gcc -g sort_demo.c -o sort_demo
//author: [email protected]
//date: 2019-03-12#include 
#include 
#include void swap(int arr[], int a, int b){int tmp = arr[a];arr[a] = arr[b];arr[b] = tmp;
}void insert_sort(int arr[], int n){int i,j,t;//遍历未排序集，默认第一个元素(i=0)是有序集内的for(i=1; i0 && t0; gap/=2){for(i=gap; i=gap && tarr[j+1])swap(arr, j, j+1);}}
}void quick_sort(int arr[], int left, int right){int i,j,pivot;if(left>right)return;pivot=arr[left];i=left;j=right;while(i!=j){while(arr[j]>=pivot && iarr[j])min=j;}if(min!=i)swap(arr, min, i);}
}#define LeftChild(i) (2*(i) + 1)//构建以arr[i]为根的最大堆
void heap_adjust(int arr[], int i, int n){int child,t;for(t=arr[i]; LeftChild(i)arr[child])child++;if(t=0; i--)heap_adjust(arr, i, n);for(i=n-1; i>0; i--){swap(arr, 0, i);heap_adjust(arr, 0, i);}
}//lb=start of left half, le=end of left half;
//rb=start of right half, re=end of right half;
void merge(int arr[], int tmp_arr[], int lb, int rb, int re){int i, le, total, tmp;le=rb-1;tmp=lb;total=re-lb+1;while(lb<=le && rb<=re){if(arr[lb]<=arr[rb])tmp_arr[tmp++]=arr[lb++];elsetmp_arr[tmp++]=arr[rb++];}while(lb<=le)tmp_arr[tmp++]=arr[lb++];while(rb<=re)tmp_arr[tmp++]=arr[rb++];//copy tmp_array backfor(i=0; iarr[i])min=arr[i];}//计算桶的个数,每个桶至多10个元素num=(max-min+1)/BUCKET_DEPTH+1;bucket* pb=(bucket*)malloc(sizeof(bucket)*num);if(pb==NULL){printf("No enough memory space for allocate bucket array!!!");exit(-1);}memset(pb, 0, sizeof(bucket)*num);//将数组中的数据放入所属的桶内for(i=0; iBUCKET_DEPTH){printf("FATAL: bucket [%d] has no enough space to store item!!!", pb[idx].count);exit(-1);}//放元素进桶内pb[idx].node[pb[idx].count++]=arr[i];}pos=0;//按顺序逐个输出桶内的元素，桶内元素采用快速排序for(i=0; i0)quick_sort(pb[i].node, 0, pb[i].count-1);for(j=0; jarr[i])min=arr[i];}//申请辅助计数数组，并初始化range=max-min+1;int* parr=(int*)malloc(sizeof(int) * range);if(parr==NULL){printf("FATAL: no enough memory space to allocate counting array!!!");exit(-1);}memset(parr, 0, sizeof(int) * range);//统计数组中每个元素出现的次数for(i=0; iarr[i])min=arr[i];}//申请辅助计数数组，并初始化range=max-min+1;//printf("max:%d, min:%d, range:%d
", max, min, range);int* parr=(int*)malloc(sizeof(int) * (range+1));if(parr==NULL){printf("FATAL: no enough memory space to allocate counting array!!!");exit(-1);}memset(parr, 0, sizeof(int) * (range+1));//动态分配一个临时数据用来存放排序后的数组数据int *tmp;if((tmp=(int*)malloc(sizeof(int) * (n+1))) == NULL){printf("FATAL: no enough memory space to store sorted array!!!");exit(-1);}memset(tmp, 0, sizeof(int)*(n+1));//统计数组中每个元素出现的次数for(i=0; i=0; i--){//arr[i]在有序数组中的偏移是parr[arr[i]-min]-1tmp[parr[arr[i]-min] - 1] = arr[i];parr[arr[i]-min]--;}
/*for(i=0; i

下面是快速排序的运行截图：

 

参考文献

[1].Weiss《数据结构与算法分析：c语言描述》(第二版)第七章

[2].Kyle Loudon著，肖翔，陈舸译《算法精解--c语言描述》(中文版)p.255

更多相关：

  • 剑指offer: 面试题40. 最小的k个数

    题目：最小的k个数 入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。 示例 1： 输入：arr = [3,2,1], k = 2 输出：[1,2] 或者 [2,1] 示例 2： 输入：arr = [0,1,2,1], k = 1 输出：[0...

  • JS如何深度复制对象和数组，避免指针变量引用修改值

    //自定义深度复制对象or数组的递归方法---------------------------------------- let copyObjOrArr = o => {let isArray = o instanceof Array;let isObject = o instanceof Object;if (!isObject)...

  • 【数组方法大合集】原生js数组array常用工具方法大合集

    var array = {/* 数组求和*/sum: arr => eval(arr.join("+")),/* 判断一个数组(支持一个字符串)里面的是否有任何一个元素被包含在了某个字符串里面 */isStringContain(str, arr) {Array.isArray(arr) || (arr = [arr]);for (v...

  • 快速排序的两种实现方法(c语言版本)

    经过调研发现，对任意无序整数数组，快速排序有两种实现方法，这里简单阐述下思路： 思路一：随意选择一个基准元，一般选择数组的起始元或末尾元，Weiss这本书上特意搞了个算法来选择基准元，……，总之就是基准元的选择要尽量随机。选定基准元之后，比如选择数组起始元为基准元，从数组右边开始，向左边遍历，遇到比基准元大的跳过，直至遇到比基准元小...

  • java 读取excel_Java12POI操作Excel

            Apache POI是一个开源的利用Java读写Excel，WORD等微软OLE2组件文档的项目。        我的需求是对Excel的数据进行导入或将数据以Excel的形式导出。先上简单的测试代码：package com.xing.studyTest.poi;import java.io.FileInputSt...

  • C++ 生成随机数

    要取得[a,b)的随机整数，使用(rand() % (b-a))+ a; 要取得[a,b]的随机整数，使用(rand() % (b-a+1))+ a; 要取得(a,b]的随机整数，使用(rand() % (b-a))+ a + 1; 通用公式:a + rand() % n；其中的a是起始值，n是整数的范围。 要取得a到b之间的...

  • 基于C++的本征图像分解(Intrinsic Image Decomposition)

    利用本征图像分解(Intrinsic Image Decomposition)算法，将图像分解为shading(illumination) image 和 reflectance(albedo) image，计算图像的reflectance image。 Reflectance Image 是指在变化的光照条件下能够维持不变的图像部分...

  • 剑指offer：面试题39. 数组中出现次数超过一半的数字

    题目：面试题39. 数组中出现次数超过一半的数字 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。 示例 1: 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2 限制： 1 <= 数组长度 <= 50000 解题： cl...

  • 剑指offer：面试题33. 二叉搜索树的后序遍历序列

    题目：二叉搜索树的后序遍历序列 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。 参考以下这颗二叉搜索树：      5     /    2   6   /  1   3示例 1： 输入: [1,6,3,2,5] 输出...

  • 利用sort对多字段排序

    sort sort_demo.txt -k1,1 -k2n,2...

©2024 11GX.COM