常见排序算法可以分为两大类：
- 比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
- 非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。
稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。
直接插入排序
#include<stdio.h> #define N 10 int main() { int a[N] = { 3,2,8,5,4,7,6,9,1,10 }; //定义数组； printf("原始数据为:\n"); for (int i = 0; i < N; i++) //输出原始数据； printf("%d ", a[i]); printf("\n\n"); //对数组a进行直接插入排序，n为数组的长度； //[0,end]有序，end+1位置的值插入[0，end]，让[0，end+1]有序。 for (int i = 0; i < N-1; i++) { int end = i; int tmp = a[end + 1]; while (end >= 0) { if (a[end] > tmp) { a[end + 1] = a[end]; end--; } else {break;} } a[end + 1] = tmp; } printf("排序后数据为:\n"); for (int i = 0; i < N; i++) //输出排序后数据； printf("%d ", a[i]); return 0; }
折半插入排序
//折半插入排序； #include<stdio.h> #define N 10 int main(void) { int a[N] = { 3,2,8,5,4,7,6,9,1,10 }; //定义数组； printf("原始数据为:\n"); for (int i = 0; i < N; i++) //输出原始数据； printf("%d ", a[i]); printf("\n\n"); //对数组a进行折半插入排序，n为数组的长度； { for (int i = 1; i < N; i++) { int x = a[i]; //将需要进行插入排序的元素赋值给x； int low = 0, high = i - 1; //设置折半的头和尾； while (low <= high) { int mid = (low + high) / 2; //设置中间元素，与插入的元素进行比较； if (x < a[mid]) //比较； high = mid - 1; else low = mid + 1; } for (int j = i - 1; j >= low; j--) //记录依次向后移； a[j + 1] = a[j]; //将当前这个值赋给这个元素的后一个元素； a[low] = x; //插入记录； } } printf("使用插入排序后的数据为:\n"); for (int i = 0; i < N; i++) printf("%d ", a[i]); printf("\n"); return 0; }
希尔排序
#include<stdio.h> #define N 10 int main() { int a[N] = { 3,2,8,5,4,7,6,9,1,10 }; //定义数组； printf("原始数据为:\n"); for (int i = 0; i < N; i++) //输出原始数据； printf("%d ", a[i]); printf("\n\n"); //对数组a进行希尔排序，n为数组的长度； int gop = 5; while (gop > 1) { gop = gop - 2; //printf("%d\n", gop); for (int i = 0; i < N - gop; i++) { int end = i; int tmp = a[end + gop]; while (end >= 0) { if (a[end] > tmp) { a[end + gop] = a[end]; end = end - gop; } else { break; } } a[end + gop] = tmp; } } printf("排序后数据为:\n"); for (int i = 0; i < N; i++) //输出排序后数据； printf("%d ", a[i]); return 0; }
简单选择排序
#include<stdio.h> #define N 10 void Swap(int* a, int* b) { //定义了类型为int*的指针a,b，指针指向的类型为int int tmp = *a; //将指针a所指向的地址中的内容赋值给tmp *a = *b; //将指针b所指向的地址中的内容赋值给指针a所指向的地址中的内容 b = tmp; } void SelectSort(int* a, int n) { for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { if (a[i] > a[j]) { int num = a[i]; a[i] = a[j]; a[j] = num; } } } } int main() { int a[N] = { 3,2,8,5,4,7,6,9,1,10 }; //定义数组； printf("原始数据为:\n"); for (int i = 0; i < N; i++) //输出原始数据； printf("%d ", a[i]); printf("\n\n"); SelectSort(a, sizeof(a)/sizeof(int)); printf("排序后数据为:\n"); for (int i = 0; i < N; i++) //输出排序后数据； printf("%d ", a[i]); return 0; }
堆排序
#include<stdio.h>、 #define N 10 //交换,传地址 void Swap(int* child, int* parent) { int tmp = *child; *child = *parent; *parent = tmp; } //向下调整算法 //从根节点开始，如果是建立小堆选出左右孩子中小的那一个，跟父亲比较，如果比父亲小就交换 void AdjustDwon(int* a, int n, int root)//建小堆 { int parent = root;//父亲节点 int child = parent * 2 + 1;//默认是左孩子 while (child < n)//叶子节点下标不会超过数组总下标数n { //选出左右孩子中最小的那一个 if (child + 1 < n && a[child + 1] < a[child]) { child += 1;//用a[child]与父亲节点a[parent]比较 } if (a[child] < a[parent]) { //交换,传地址 Swap(&a[child], &a[parent]); //交换后，将child,作为根节点继续向下调整，持续建堆 parent = child; //新的左孩子 child = parent * 2 + 1; } else { break;//如果不用交换，直接结束循环 } } } //堆的建立 //大堆要求：树中所有的父亲都>=孩子,根是最大的 //小堆要求：书中所有的父亲都<=孩子,根是最小的 //建大堆排升序，建小堆排降序 //建堆的时间复杂度是O(N); void HeapSort(int* a, int n) { //找父亲节点 for (int i = (n - 1 - 1) / 2; i >= 0; --i) { //向下调整算法 AdjustDwon(a, n, i); } //大堆或小堆建立完毕，排序 //用主根节点与最后一个节点交换位置 int end = n - 1; while (end > 0) { //交换，传地址 Swap(&a[0], &a[end]); //继续向下调整 AdjustDwon(a, end, 0); --end; } } //选择排序—堆排序 int main() { int a[N] = { 9,2,5,4,3,1,6,7,8,10 }; //堆的建立 HeapSort(a, sizeof(a) / sizeof(int)); for (int i = 0; i < N; ++i) { printf("%d ", a[i]); } return 0; } /*void Printf(int* a, int n) { for (int i = 0; i < n; ++i) { printf("%d ", a[i]); } }*/
冒泡排序
#include<stdio.h> #define N 10 int main() { int a[N] = { 3,2,8,5,4,7,6,9,1,10 }; //定义数组； printf("原始数据为:\n"); for (int i = 0; i < N; i++) //输出原始数据； printf("%d ", a[i]); printf("\n\n"); for (int i = 0; i < N; i++)//控制交换次数 { for (int j = 0; j < N - i - 1; j++)//向后冒泡 ,控制边界 { if (a[j] > a[j + 1])//如果前一个值大于后一个值,交换. { int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t; } } } printf("排序后数据为:\n"); for (int i = 0; i < N; i++) //输出排序后数据； printf("%d ", a[i]); return 0; }
快速排序
#include<stdio.h> #define N 10 void QuickSort(int* a, int low, int high) { if (low < high) { int i = low; int j = high; int k = a[low]; while (i < j) { while (i < j && a[j] >= k) j--; // 从右向左找第一个小于k的数 if (i < j) a[i++] = a[j]; while (i < j && a[i] < k) i++; // 从左向右找第一个大于等于k的数 if (i < j) a[j--] = a[i]; } a[i] = k; // 递归调用 QuickSort(a, low, i - 1); QuickSort(a, i + 1, high); } } int main() { int a[N] = { 3,2,8,5,4,7,6,9,1,10 }; //定义数组； printf("原始数据为:\n"); for (int i = 0; i < N; i++) //输出原始数据； printf("%d ", a[i]); printf("\n\n"); QuickSort(a, 0, N - 1); printf("排序后数据为:\n"); for (int i = 0; i < N; i++) //输出排序后数据； printf("%d ", a[i]); return 0; }
联系方式:
（qq）:2965191336 邮件：2965191336@qq.com
文章存在借鉴，如有侵权请联系修改删除！
