C 排序算法
冒泡排序
冒泡排序(英语:Bubble Sort)是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序(如从大到小、首字母从A到Z)错误就把他们交换过来。
过程演示:
实例
#include<stdio.h>// 函数声明voidbubble_sort(intarr[], intlen);
intmain(){intarr[] = {22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70};
intlen = sizeof(arr) / sizeof(arr[0]); // 计算数组长度bubble_sort(arr, len); // 调用冒泡排序函数// 打印排序后的数组for(inti = 0; i < len; i++){printf("%d ", arr[i]);
}return0;
}// 冒泡排序函数voidbubble_sort(intarr[], intlen){for(inti = 0; i < len - 1; i++){for(intj = 0; j < len - 1 - i; j++){// 交换元素位置if(arr[j] > arr[j + 1]){inttemp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}}}}
选择排序
选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。
过程演示:
实例
#include<stdio.h>// 函数声明voidselection_sort(inta[], intlen);
intmain(){intarr[] = {22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70};
intlen = sizeof(arr) / sizeof(arr[0]); // 计算数组长度selection_sort(arr, len); // 调用选择排序函数// 打印排序后的数组for(inti = 0; i < len; i++){printf("%d ", arr[i]);
}return0;
}// 选择排序函数voidselection_sort(inta[], intlen){for(inti = 0; i < len - 1; i++){intmin = i; // 记录最小值的位置,第一个元素默认最小for(intj = i + 1; j < len; j++){if(a[j] < a[min]){// 找到目前最小值min = j; // 记录最小值的位置}}// 交换两个变量if(min != i){inttemp = a[min];
a[min] = a[i];
a[i] = temp;
}}}/*
// 自定义交换函数
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
*/
插入排序
插入排序(英语:Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到 {\displaystyle O(1)} {\displaystyle O(1)}的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后
挪位,为最新元素提供插入空间。过程演示:
实例
#include<stdio.h>// 函数声明voidinsertion_sort(intarr[], intlen);
intmain(){intarr[] = {22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70};
intlen = sizeof(arr) / sizeof(arr[0]); // 计算数组长度insertion_sort(arr, len); // 调用插入排序函数// 打印排序后的数组for(inti = 0; i < len; i++){printf("%d ", arr[i]);
}return0;
}// 插入排序函数voidinsertion_sort(intarr[], intlen){for(inti = 1; i < len; i++){inttemp = arr[i]; // 当前待插入的元素intj = i;
// 向右移动大于temp的元素while(j > 0 && arr[j - 1] > temp){arr[j] = arr[j - 1];
j--;
}arr[j] = temp; // 插入元素到正确位置}}
希尔排序
希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的:
- 插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率
- 但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位
过程演示:
实例
#include<stdio.h>// 函数声明voidshell_sort(intarr[], intlen);
intmain(){intarr[] = {22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70};
intlen = sizeof(arr) / sizeof(arr[0]); // 计算数组长度shell_sort(arr, len); // 调用希尔排序函数// 打印排序后的数组for(inti = 0; i < len; i++){printf("%d ", arr[i]);
}return0;
}// 希尔排序函数voidshell_sort(intarr[], intlen){// 计算初始间隔for(intgap = len / 2; gap > 0; gap /= 2){// 对每个间隔进行插入排序for(inti = gap; i < len; i++){inttemp = arr[i]; // 当前待插入的元素intj = i;
// 移动大于temp的元素while(j >= gap && arr[j - gap] > temp){arr[j] = arr[j - gap];
j -= gap;
}arr[j] = temp; // 插入元素到正确位置}}}
归并排序
把数据分为两段,从两段中逐个选最小的元素移入新数据段的末尾。
可从上到下或从下到上进行。
过程演示:
迭代法
#include<stdio.h>#include<stdlib.h>// 函数声明intmin(intx, inty);
voidmerge_sort(intarr[], intlen);
intmain(){intarr[] = {22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70};
intlen = sizeof(arr) / sizeof(arr[0]); // 计算数组长度merge_sort(arr, len); // 调用归并排序函数// 打印排序后的数组for(inti = 0; i < len; i++){printf("%d ", arr[i]);
}return0;
}// 返回两个数中的最小值intmin(intx, inty){returnx < y ? x : y;
}// 归并排序函数voidmerge_sort(intarr[], intlen){int* a = arr;
int* b = (int*)malloc(len * sizeof(int));
if(b == NULL){// 检查内存分配是否成功fprintf(stderr, "Memory allocation failed\n");
exit(EXIT_FAILURE);
}for(intseg = 1; seg < len; seg += seg){for(intstart = 0; start < len; start += seg + seg){intlow = start;
intmid = min(start + seg, len);
inthigh = min(start + seg + seg, len);
intk = low;
intstart1 = low, end1 = mid;
intstart2 = mid, end2 = high;
// 合并两个子数组while(start1 < end1 && start2 < end2){b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
}while(start1 < end1){b[k++] = a[start1++];
}while(start2 < end2){b[k++] = a[start2++];
}}// 交换数组指针int* temp = a;
a = b;
b = temp;
}// 如果a和arr不相同,则将a的内容复制回arrif(a != arr){for(inti = 0; i < len; i++){b[i] = a[i];
}b = a;
}free(b); // 释放内存}
递归法
#include<stdio.h>#include<stdlib.h>#include<string.h>// 函数声明voidmerge_sort_recursive(intarr[], intreg[], intstart, intend);
voidmerge_sort(intarr[], constintlen);
intmain(){intarr[] = {22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70};
intlen = sizeof(arr) / sizeof(arr[0]); // 计算数组长度merge_sort(arr, len); // 调用归并排序函数// 打印排序后的数组for(inti = 0; i < len; i++){printf("%d ", arr[i]);
}return0;
}// 递归实现归并排序voidmerge_sort_recursive(intarr[], intreg[], intstart, intend){if(start >= end)return;
intmid = start + (end - start) / 2;
intstart1 = start, end1 = mid;
intstart2 = mid + 1, end2 = end;
merge_sort_recursive(arr, reg, start1, end1);
merge_sort_recursive(arr, reg, start2, end2);
intk = start;
while(start1 <= end1 && start2 <= end2){reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
}while(start1 <= end1){reg[k++] = arr[start1++];
}while(start2 <= end2){reg[k++] = arr[start2++];
}// 使用memcpy进行数组复制,提高效率memcpy(arr + start, reg + start, (end - start + 1) * sizeof(int));
}// 归并排序入口函数voidmerge_sort(intarr[], constintlen){int* reg = (int*)malloc(len * sizeof(int));
if(reg == NULL){// 检查内存分配是否成功fprintf(stderr, "Memory allocation failed\n");
exit(EXIT_FAILURE);
}merge_sort_recursive(arr, reg, 0, len - 1);
free(reg); // 释放内存}
快速排序
在区间中随机挑选一个元素作基准,将小于基准的元素放在基准之前,大于基准的元素放在基准之后,再分别对小数区与大数区进行排序。
过程演示:
迭代法
#include<stdio.h>// 范围结构体typedefstruct_Range{intstart, end;
}Range;
// 创建新的范围Rangenew_Range(ints, inte){Ranger;
r.start = s;
r.end = e;
returnr;
}// 交换两个整数voidswap(int *x, int *y){intt = *x;
*x = *y;
*y = t;
}// 快速排序函数voidquick_sort(intarr[], constintlen){if(len <= 0)return; // 避免 len 等于负值时引发段错误(Segment Fault)Ranger[len];
intp = 0;
r[p++] = new_Range(0, len - 1);
while(p > 0){Rangerange = r[--p];
if(range.start >= range.end)continue;
intmid = arr[(range.start + range.end) / 2]; // 选取中间点为基准点intleft = range.start, right = range.end;
do{while(arr[left] < mid) ++left; // 检测基准点左侧是否符合要求while(arr[right] > mid) --right; // 检测基准点右侧是否符合要求if(left <= right){swap(&arr[left], &arr[right]);
left++;
right--; // 移动指针以继续}}while(left <= right);
if(range.start < right)r[p++] = new_Range(range.start, right);
if(range.end > left)r[p++] = new_Range(left, range.end);
}}intmain(){intarr[] = {22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70};
intlen = sizeof(arr) / sizeof(arr[0]); // 计算数组长度quick_sort(arr, len); // 调用快速排序函数// 打印排序后的数组for(inti = 0; i < len; i++){printf("%d ", arr[i]);
}return0;
}
递归法
#include<stdio.h>// 交换两个整数voidswap(int *x, int *y){intt = *x;
*x = *y;
*y = t;
}// 递归实现快速排序voidquick_sort_recursive(intarr[], intstart, intend){if(start >= end)return;
intmid = arr[end];
intleft = start, right = end - 1;
while(left < right){while(left < right && arr[left] < mid)left++;
while(left < right && arr[right] >= mid)right--;
swap(&arr[left], &arr[right]);
}if(arr[left] >= arr[end])swap(&arr[left], &arr[end]);
elseleft++;
quick_sort_recursive(arr, start, left - 1);
quick_sort_recursive(arr, left + 1, end);
}// 快速排序入口函数voidquick_sort(intarr[], intlen){quick_sort_recursive(arr, 0, len - 1);
}intmain(){intarr[] = {22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70};
intlen = sizeof(arr) / sizeof(arr[0]); // 计算数组长度quick_sort(arr, len); // 调用快速排序函数// 打印排序后的数组for(inti = 0; i < len; i++){printf("%d ", arr[i]);
}return0;
}