?-以下都是调用函数-遇到相关排序题直接套用即可
选择排序
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;
}