一，直接插入排序
二，折半插入排序
三，希尔排序
四，简单选择排序
五，堆排序
六，冒泡排序
七，快速排序
八，归并排序
九，基数排序web
一，插入排序算法
#include <stdio.h> // 分类 ------------- 内部比较排序 // 数据结构 ---------- 数组 // 最差时间复杂度 ---- 最坏状况为输入序列是降序排列的,此时时间复杂度O(n^2) // 最优时间复杂度 ---- 最好状况为输入序列是升序排列的,此时时间复杂度O(n) // 平均时间复杂度 ---- O(n^2) // 所需辅助空间 ------ O(1) // 稳定性 ------------ 稳定 void InsertionSort(int A[], int n) { for (int i = 1; i < n; i++) // 相似抓扑克牌排序 { int get = A[i]; // 右手抓到一张扑克牌 int j = i - 1; // 拿在左手上的牌老是排序好的 while (j >= 0 && A[j] > get) // 将抓到的牌与手牌从右向左进行比较 { A[j + 1] = A[j]; // 若是该手牌比抓到的牌大，就将其右移 j--; } A[j + 1] = get; // 直到该手牌比抓到的牌小(或两者相等)，将抓到的牌插入到该手牌右边(相等元素的相对次序未变，因此插入排序是稳定的) } } int main() { int A[] = { 6, 5, 3, 1, 8, 7, 2, 4 };// 从小到大插入排序 int n = sizeof(A) / sizeof(int); InsertionSort(A, n); printf("插入排序结果："); for (int i = 0; i < n; i++) { printf("%d ", A[i]); } printf("\n"); return 0; }
二，二分插入排序api
#include <stdio.h> // 分类 -------------- 内部比较排序 // 数据结构 ---------- 数组 // 最差时间复杂度 ---- O(n^2) // 最优时间复杂度 ---- O(nlogn) // 平均时间复杂度 ---- O(n^2) // 所需辅助空间 ------ O(1) // 稳定性 ------------ 稳定 void InsertionSortDichotomy(int A[], int n) { for (int i = 1; i < n; i++) { int get = A[i]; // 右手抓到一张扑克牌 int left = 0; // 拿在左手上的牌老是排序好的，因此能够用二分法 int right = i - 1; // 手牌左右边界进行初始化 while (left <= right) // 采用二分法定位新牌的位置 { int mid = (left + right) / 2; if (A[mid] > get) right = mid - 1; else left = mid + 1; } for (int j = i - 1; j >= left; j--) // 将欲插入新牌位置右边的牌总体向右移动一个单位 { A[j + 1] = A[j]; } A[left] = get; // 将抓到的牌插入手牌 } } int main() { int A[] = { 5, 2, 9, 4, 7, 6, 1, 3, 8 };// 从小到大二分插入排序 int n = sizeof(A) / sizeof(int); InsertionSortDichotomy(A, n); printf("二分插入排序结果："); for (int i = 0; i < n; i++) { printf("%d ", A[i]); } printf("\n"); return 0; }
五，堆排序数组
#include <stdio.h> // 分类 -------------- 内部比较排序 // 数据结构 ---------- 数组 // 最差时间复杂度 ---- O(nlogn) // 最优时间复杂度 ---- O(nlogn) // 平均时间复杂度 ---- O(nlogn) // 所需辅助空间 ------ O(1) // 稳定性 ------------ 不稳定 void Swap(int A[], int i, int j) { int temp = A[i]; A[i] = A[j]; A[j] = temp; } void Heapify(int A[], int i, int size) // 从A[i]向下进行堆调整 { int left_child = 2 * i + 1; // 左孩子索引 int right_child = 2 * i + 2; // 右孩子索引 int max = i; // 选出当前结点与其左右孩子三者之中的最大值 if (left_child < size && A[left_child] > A[max]) max = left_child; if (right_child < size && A[right_child] > A[max]) max = right_child; if (max != i) { Swap(A, i, max); // 把当前结点和它的最大(直接)子节点进行交换 Heapify(A, max, size); // 递归调用，继续从当前结点向下进行堆调整 } } int BuildHeap(int A[], int n) // 建堆，时间复杂度O(n) { int heap_size = n; for (int i = heap_size / 2 - 1; i >= 0; i--) // 从每个非叶结点开始向下进行堆调整 Heapify(A, i, heap_size); return heap_size; } void HeapSort(int A[], int n) { int heap_size = BuildHeap(A, n); // 创建一个最大堆 while (heap_size > 1) // 堆（无序区）元素个数大于1，未完成排序 { // 将堆顶元素与堆的最后一个元素互换，并从堆中去掉最后一个元素 // 此处交换操做颇有可能把后面元素的稳定性打乱，因此堆排序是不稳定的排序算法 Swap(A, 0, --heap_size); Heapify(A, 0, heap_size); // 重新的堆顶元素开始向下进行堆调整，时间复杂度O(logn) } } int main() { int A[] = { 5, 2, 9, 4, 7, 6, 1, 3, 8 };// 从小到大堆排序 int n = sizeof(A) / sizeof(int); HeapSort(A, n); printf("堆排序结果："); for (int i = 0; i < n; i++) { printf("%d ", A[i]); } printf("\n"); return 0; }
六，冒泡排序数据结构
#include <stdio.h> // 分类 -------------- 内部比较排序 // 数据结构 ---------- 数组 // 最差时间复杂度 ---- O(n^2) // 最优时间复杂度 ---- 若是能在内部循环第一次运行时,使用一个旗标来表示有无须要交换的可能,能够把最优时间复杂度下降到O(n) // 平均时间复杂度 ---- O(n^2) // 所需辅助空间 ------ O(1) // 稳定性 ------------ 稳定 void Swap(int A[], int i, int j) { int temp = A[i]; A[i] = A[j]; A[j] = temp; } void BubbleSort(int A[], int n) { for (int j = 0; j < n - 1; j++) // 每次最大元素就像气泡同样"浮"到数组的最后 { for (int i = 0; i < n - 1 - j; i++) // 依次比较相邻的两个元素,使较大的那个向后移 { if (A[i] > A[i + 1]) // 若是条件改为A[i] >= A[i + 1],则变为不稳定的排序算法 { Swap(A, i, i + 1); } } } } int main() { int A[] = { 8,7,2,9,4,3,8,4,2,3 }; // 从小到大冒泡排序 int n = sizeof(A) / sizeof(int); BubbleSort(A, n); printf("冒泡排序结果："); for (int i = 0; i < n; i++) { printf("%d ", A[i]); } printf("\n"); return 0; }
七，快速排序svg
#include <stdio.h> // 分类 ------------ 内部比较排序 // 数据结构 --------- 数组 // 最差时间复杂度 ---- 每次选取的基准都是最大（或最小）的元素，致使每次只划分出了一个分区，须要进行n-1次划分才能结束递归，时间复杂度为O(n^2) // 最优时间复杂度 ---- 每次选取的基准都是中位数，这样每次都均匀的划分出两个分区，只须要logn次划分就能结束递归，时间复杂度为O(nlogn) // 平均时间复杂度 ---- O(nlogn) // 所需辅助空间 ------ 主要是递归形成的栈空间的使用(用来保存left和right等局部变量)，取决于递归树的深度，通常为O(logn)，最差为O(n) // 稳定性 ---------- 不稳定 void Swap(int A[], int i, int j) { int temp = A[i]; A[i] = A[j]; A[j] = temp; } int Partition(int A[], int left, int right) // 划分函数 { int pivot = A[right]; // 这里每次都选择最后一个元素做为基准 int tail = left - 1; // tail为小于基准的子数组最后一个元素的索引 for (int i = left; i < right; i++) // 遍历基准之外的其余元素 { if (A[i] <= pivot) // 把小于等于基准的元素放到前一个子数组末尾 { Swap(A, ++tail, i); } } Swap(A, tail + 1, right); // 最后把基准放到前一个子数组的后边，剩下的子数组既是大于基准的子数组 // 该操做颇有可能把后面元素的稳定性打乱，因此快速排序是不稳定的排序算法 return tail + 1; // 返回基准的索引 } void QuickSort(int A[], int left, int right) { if (left >= right) return; int pivot_index = Partition(A, left, right); // 基准的索引 QuickSort(A, left, pivot_index - 1); QuickSort(A, pivot_index + 1, right); } int main() { int A[] = { 5, 2, 9, 4, 7, 6, 1, 3, 8 }; // 从小到大快速排序 int n = sizeof(A) / sizeof(int); QuickSort(A, 0, n - 1); printf("快速排序结果："); for (int i = 0; i < n; i++) { printf("%d ", A[i]); } printf("\n"); return 0; }
八，归并排序函数
#include <stdio.h> #include <limits.h> // 分类 -------------- 内部比较排序 // 数据结构 ---------- 数组 // 最差时间复杂度 ---- O(nlogn) // 最优时间复杂度 ---- O(nlogn) // 平均时间复杂度 ---- O(nlogn) // 所需辅助空间 ------ O(n) // 稳定性 ------------ 稳定 void Merge(int A[], int left, int mid, int right)// 合并两个已排好序的数组A[left...mid]和A[mid+1...right] { int len = right - left + 1; int *temp = new int[len]; // 辅助空间O(n) int index = 0; int i = left; // 前一数组的起始元素 int j = mid + 1; // 后一数组的起始元素 while (i <= mid && j <= right) { temp[index++] = A[i] <= A[j] ? A[i++] : A[j++]; // 带等号保证归并排序的稳定性 } while (i <= mid) { temp[index++] = A[i++]; } while (j <= right) { temp[index++] = A[j++]; } for (int k = 0; k < len; k++) { A[left++] = temp[k]; } } void MergeSortRecursion(int A[], int left, int right) // 递归实现的归并排序(自顶向下) { if (left == right) // 当待排序的序列长度为1时，递归开始回溯，进行merge操做 return; int mid = (left + right) / 2; MergeSortRecursion(A, left, mid); MergeSortRecursion(A, mid + 1, right); Merge(A, left, mid, right); } void MergeSortIteration(int A[], int len) // 非递归(迭代)实现的归并排序(自底向上) { int left, mid, right;// 子数组索引,前一个为A[left...mid]，后一个子数组为A[mid+1...right] for (int i = 1; i < len; i *= 2) // 子数组的大小i初始为1，每轮翻倍 { left = 0; while (left + i < len) // 后一个子数组存在(须要归并) { mid = left + i - 1; right = mid + i < len ? mid + i : len - 1;// 后一个子数组大小可能不够 Merge(A, left, mid, right); left = right + 1; // 前一个子数组索引向后移动 } } } int main() { int A1[] = { 6, 5, 3, 1, 8, 7, 2, 4 }; // 从小到大归并排序 int A2[] = { 6, 5, 3, 1, 8, 7, 2, 4 }; int n1 = sizeof(A1) / sizeof(int); int n2 = sizeof(A2) / sizeof(int); MergeSortRecursion(A1, 0, n1 - 1); // 递归实现 MergeSortIteration(A2, n2); // 非递归实现 printf("递归实现的归并排序结果："); for (int i = 0; i < n1; i++) { printf("%d ", A1[i]); } printf("\n"); printf("非递归实现的归并排序结果："); for (int i = 0; i < n2; i++) { printf("%d ", A2[i]); } printf("\n"); return 0; }
下面是全部排序算法，可能会有错误。测试
#include<stdio.h> #include<stdlib.h> #include<string.h> //输出模块 void Output(int a[],int length) { for (int j = 0; j < length; j++) { printf("%d\t", a[j]); } printf("\n\n=============================\n\n"); } //1、直接插入排序（插入排序） //一、思想：最基本的插入排序，将第i个插入到前i - 1个中的适当位置。 //二、时间复杂度：O(n^2)。 //三、空间复杂度：O(1)。 //四、稳定性：稳定。 void InsSort(int a[],int length) { int temp = 0, j = 0, i = 0; for (i = 1; i <= length; i++) { temp = a[i]; //取出一个未排序的数据 for (j = i - 1; j >= 0 && temp < a[j]; j--) { a[j + 1] = a[j]; //向后移动数据 } a[j + 1] = temp; //插入数据到序列 } } //2、折半插入排序（插入排序） //一、思想：由于是已经肯定了前部分是有序序列，因此在查找插入位置的时候能够用折半查找的方法进行查找，提升效率。 //二、时间复杂度：比较时的时间减为O(nlogn)，可是移动元素的时间耗费未变，因此老是得时间复杂度仍是O(n^2)。 //三、空间复杂度：S(n) = O(1)。 //四、稳定性：稳定。 void BinSort(int a[], int length) { int temp = 0, j = 0, i = 0; for (i = 1; i <= length; i++) { temp = a[i]; //待插入元素 int low = 0, high = i - 1; while (low <= high) { int m = (low + high) / 2; //折半 if (temp < a[m]) //插入点在低半区 { high = m - 1; } else //插入点在高半区 { low = m + 1; } } //向后移动数据 for (j = i - 1; j >= low; j--) { a[j + 1] = a[j]; } a[j + 1] = temp;//插入数据到序列 } } //3、希尔排序（插入排序） //一、思想：又称缩小增量排序法。把待排序序列分红若干较小的子序列，而后逐个使用直接插入排序法排序，最后再对一个较为有序的序列进行一次排序 // 主要是为了减小移动的次数，提升效率。原理应该就是从无序到渐渐有序，要比直接从无序到有序移动的次数会少一些。 //二、时间复杂度：O(n^1.5) //三、空间复杂度：O(1) //四、稳定性：不稳定。 {2, 4, 1, 2}，2和1一组4和2一组，进行希尔排序，第一个2和最后一个2会发生位置上的变化。 void ShellInsert(int a[],int length) { int temp = 0, j = 0, i = 0; int step = length / 2; //取增量 //保证最后一个增量为1 while (step >= 1) { for (i = step; i < length; i++) { temp = a[i]; //每两个增量间隔的数据比较，将小数据向前移动 for (j = i - step; j >= 0 && temp < a[j]; j -= step) { a[j + step] = a[j]; } a[j + step] = temp; //保存数据 } step /= 2; //缩小增量 } } //4、简单选择排序（选择排序） //一、思想：每一趟排序将会选择出最小的(或者最大的)值，顺序放在已排好序的数列的后面 //二、时间复杂度：O(n^2) //三、空间复杂度：O(1) //四、稳定性：不稳定 void SelectionSort(int a[], int length) { int temp = 0, j = 0, i = 0; for (i = 0; i < length; i++) { for (j = i + 1; j < length; j++) { //前一个数大于后一个数，交换 if (a[i] > a[j]) { temp = a[j]; a[j] = a[i]; a[i] = temp; } } } } //5、堆排序（选择排序） //一、思想：堆排序利用这种堆这种数据结构所设计的一种排序算法，能够利用数组的特色快速定位指定索引的元素 //二、时间复杂度：O(nlogn)。 //三、空间复杂度：O(1)。 //四、稳定性：不稳定。 void heapAdjust(int a[], int parent, int length) { int temp = a[parent]; // temp保存当前父节点 int child = 2 * parent + 1;// 先得到左孩子 while (child < length) { // 若是有右孩子结点，而且右孩子结点的值大于左孩子结点，则选取右孩子结点 if (child + 1 < length && a[child] < a[child + 1]) { child++; } // 若是父结点的值已经大于孩子结点的值，则直接结束 if (temp >= a[child]) break; // 把孩子结点的值赋给父结点 a[parent] = a[child]; // 选取孩子结点的左孩子结点,继续向下筛选 parent = child; child = 2 * child + 1; } a[parent] = temp; } void HeadSort(int a[], int length) { int i; // 循环创建初始堆 // 从 0 到 length/2 ,这些都是有孩子的节点 // 没孩子的节点构造大顶堆就无心义了 for (i = length / 2; i >= 0; i--) { heapAdjust(a, i, length); } // 进行n-1次循环，完成排序 for (i = length; i > 0; i--) { int temp = a[0]; a[0] = a[i]; a[i] = temp; // 筛选 a[0] 结点，获得i-1个结点的堆 heapAdjust(a, 0, i); } } //6、冒泡排序（交换排序） //一、思想：将序列当中的左右元素，依次比较，保证左边的元素始终小于右边的元素。 //二、时间复杂度：O(n^2) //三、空间复杂度:O(1) //四、稳定性：稳定 void Swap(int A[], int i, int j) { int temp = A[i]; A[i] = A[j]; A[j] = temp; } void BubbleSort(int A[], int n) { for (int j = 0; j < n - 1 ; j++) // 每次最大元素就像气泡同样"浮"到数组的最后 { for (int i = 0; i < n - 1 - j; i++) // 依次比较相邻的两个元素,使较大的那个向后移 { if (A[i] > A[i + 1]) // 若是条件改为A[i] >= A[i + 1],则变为不稳定的排序算法 { Swap(A, i, i + 1); } } } } //7、快速排序 //思想：经过一趟排序将待排记录分割成两个部分，其中一部分记录关键字均比另外一部分记录的关键字小，则能够分别对这两部分关键字继续排序，以达到整个序列有序的目的。 //时间复杂度：O(nlogn), 最坏的状况下为O(n^2) //空间复杂度：O(1) //稳定性:不稳定 //本质就是, 找一个基位(枢轴, 分水岭, 做用是左边的都比它小, 右边的都比它大.可随机, 取名base //首先从序列最右边开始找比base小的 //若是小, 换位置, 从而base移到刚才右边(比较时比base小)的位置(记为临时的high位), 这样base右边的都比base大 //而后, 从序列的最左边开始找比base大的 //若是大, 换位置, 从而base移动到刚才左边(比较时比base大)的位置(记为临时的low位), 这样base左边的都比base小 //循环以上两步, 直到 low == high, 这使才真正的找到了枢轴, 分水岭.返回这个位置, 分水岭左边和右边的序列, 分别再来递归 // 分水岭,基位,左边的都比这个位置小,右边的都大 int partition(int a[], int low, int high) { int base = a[low]; //用子表的第一个记录作枢轴(分水岭)记录 while (low < high) { //更改下面两个while循环中的<=和>=，便可获取到从大到小排列 //从表的两端交替向中间扫描，从小到大排列 while (low < high && a[high] >= base)high--; //若是高位小于base,base赋值给当前high位,base挪到(互换)到了这里,high位右边的都比base大 int temp = a[high]; a[high] = a[low]; a[low] = temp; while (low < high && a[low] <= base)low++; //若是低位大于base temp = a[high]; a[high] = a[low]; a[low] = temp; } //如今low=heigh return low; } void QuickSort(int a[], int low, int high) { if (low < high) { int division = partition(a, low, high); QuickSort(a, low, division - 1); QuickSort(a, division + 1, high); } } //8、归并排序 //思想：归并排序是将两个或两个以上的有序表组合成一个有序表，该算法是采用分治法实现 //时间复杂度：O(nlogn) //空间复杂度：O(n) //稳定性：稳定 //归并排序其实要作两件事： //（1）“分解”——将序列每次折半划分。 //（2）“合并”——将划分后的序列段两两合并后排序。 void Merge(int a[], int low, int mid, int high)//合并 { int i = low; // i是第一段序列的下标 int j = mid + 1; // j是第二段序列的下标 int k = 0; // k是临时存放合并序列的下标 int a2[100]; // 扫描第一段和第二段序列，直到有一个扫描结束 while (i <= mid && j <= high) { // 判断第一段和第二段取出的数哪一个更小，将其存入合并序列，并继续向下扫描 if (a[i] <= a[j]) { a2[k] = a[i]; i++; k++; } else { a2[k] = a[j]; j++; k++; } } // 若第一段序列还没扫描完，将其所有复制到合并序列 while (i <= mid) { a2[k] = a[i]; i++; k++; } // 若第二段序列还没扫描完，将其所有复制到合并序列 while (j <= high) { a2[k] = a[j]; j++; k++; } // 将合并序列复制到原始序列中 for (k = 0, i = low; i <= high; i++, k++) { a[i] = a2[k]; } } void MergePass(int a[], int gap, int length)//分解 { int i = 0; // 归并gap长度的两个相邻子表 for (i = 0; i + 2 * gap - 1 <= length; i = i + 2 * gap) { Merge(a, i, i + gap - 1, i + 2 * gap - 1); } // 余下两个子表，后者长度小于gap if (i + gap - 1 <= length) { Merge(a, i, i + gap - 1, length); } } void MergeSort(int a[],int length) { for (int gap = 1; gap <= length; gap = 2 * gap) { MergePass(a, gap, length); } } //9、基数排序 //思想：基数是按照低位先排序，而后收集；再按高位排序，而后再收集，依次类推，直到最高位。 //注：表示关键词分类到radix(基数)个盒子，在关键词为数字时，基数为10，当关键词为字母时，基数为26 //时间复杂度：O(n + d) //空间复杂度：O(n) //稳定性：稳定 //================================ //=============主函数============= //================================ //选择界面 int main() { // a 存储整数的数组，最大100位 // i 计数器，记载a的长度 // p 指向a数组首地址的指针 //输入 int a[100], i; int *p = a; printf("请输入要排序的数（以空格隔开，以回车结束）："); for (i = 0;; i++) { scanf("%d", &a[i]); if (getchar() == '\n')break; } i+=1; //测试输出 printf("\n=============================\n\n"); printf("输入的数组为：\n"); Output(p, i); printf("请选择排序算法(输入其余字符退出)：\n"); printf("一、直接插入排序\n"); //插入排序 printf("二、折半插入排序\n"); //插入排序 printf("三、希尔排序\n"); //插入排序 printf("四、简单选择排序\n"); //选择排序 printf("五、堆排序\n"); //选择排序 printf("六、冒泡排序\n"); //交换排序 printf("七、快速排序\n"); //交换排序 printf("八、归并排序\n"); //printf("九、基数排序\n"); int choose = 0; scanf("%d", &choose); switch (choose) { case 1:InsSort(p, i); break; case 2:BinSort(p, i); break; case 3:ShellInsert(p, i); break; case 4:SelectionSort(p, i); break; case 5:HeadSort(p, i); break; case 6:BubbleSort(p, i); break; case 7:QuickSort(p, 0, i); break; case 8:MergeSort(p, i); break; //case 9: break; default:exit(0); break;//输入其余数字退出 } printf("\n=============================\n\n"); printf("排序后数组为：\n"); Output(p, i);//输出排序后的数组 system("pause"); }