下载文档原格式
⼗⼤经典排序算法总结最近⼏天在研究算法，将⼏种排序算法整理了⼀下，便于对这些排序算法进⾏⽐较，若有错误的地⽅，还请⼤家指正0、排序算法说明0.1 排序术语稳定：如果a=b,且a原本排在b前⾯，排序之后a仍排在b的前⾯不稳定：如果a=b,且a原本排在b前⾯，排序之后排在b的后⾯时间复杂度：⼀个算法执⾏所耗费的时间空间复杂度：⼀个算法执⾏完所需内存的⼤⼩内排序：所有排序操作都在内存中完成外排序：由于数据太⼤，因此把数据放在磁盘中，⽽排序通过磁盘和内存的数据传输才能进⾏0.2算法时间复杂度、空间复杂度⽐较0.3名词解释n:数据规模k:桶的个数In-place:占⽤常数内存，不占⽤额外内存Out-place:占⽤额外内存0.4算法分类1.冒泡排序冒泡排序是⼀种简单的排序算法。
它重复地⾛访过要排序的数列，⼀次⽐较两个元素，如果它们的顺序错误就把它们交换过来。
⾛访数列的⼯作是重复地进⾏直到没有再需要交换，也就是说该数列已经排序完成。
这个算法的名字由来是因为越⼩的元素会经由交换慢慢“浮”到数列的顶端1.1算法描述⽐较相邻的元素，如果前⼀个⽐后⼀个打，就交换对每⼀对相邻元素做同样的⼯作，从开始第⼀对到结尾最后⼀对，这样在最后的元素应该会是最⼤的数针对所有的元素重复以上的步骤，除了最后⼀个重复步骤1-3，知道排序完成1.2动图演⽰1.3代码实现public static int[] bubbleSort(int[] array) {if (array.length == 0)return array;for (int i = 0; i < array.length; i++)for (int j = 0; j < array.length - 1 - i; j++)if (array[j + 1] < array[j]) {int temp = array[j + 1];array[j + 1] = array[j];array[j] = temp;}return array;}1.4算法分析最佳情况：T(n) = O(n) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(n2)2.选择排序表现简单直观的最稳定的排序算法之⼀，因为⽆论什么数据都是O(n2)的时间复杂度，⾸先在未排序序列中找到最⼩（⼤）元素，与数组中第⼀个元素交换位置，作为排序序列的起始位置，然后再从剩余未排序元素中继续寻找最⼩（⼤）的元素，与数组中的下⼀个元素交换位置，也就是放在已排序序列的末尾2.1算法描述1.初始状态：⽆序区为R[1..n],有序区为空2.第i躺排序开始时，当前有序区和⽆序区R[1..i-1]、R[i..n]3.n-1趟结束，数组有序化2.2动图演⽰2.3代码实现public static int[] selectionSort(int[] array) {if (array.length == 0)return array;for (int i = 0; i < array.length; i++) {int minIndex = i;for (int j = i; j < array.length; j++) {if (array[j] < array[minIndex]) //找到最⼩的数minIndex = j; //将最⼩数的索引保存}int temp = array[minIndex];array[minIndex] = array[i];array[i] = temp;}return array;}2.4算法分析最佳情况：T(n) = O(n2) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(n2)3、插⼊排序是⼀种简单直观的排序算法，通过构建有序序列，对于未排序序列，在已排序序列中从后向前扫描，找到相应位置并插⼊，需要反复把已排序元素逐步向后挪位，为最新元素腾出插⼊空间3.1算法描述1.从第⼀个元素开始，该元素可以认为已经被排序2.取出下⼀个元素（h），在已排序的元素序列中从后往前扫描3.如果当前元素⼤于h，将当前元素移到下⼀位置4.重复步骤3，直到找到已排序的元素⼩于等于h的位置5.将h插⼊到该位置6.重复步骤2-53.2动图演⽰3.3代码实现public static int[] insertionSort(int[] array) {if (array.length == 0)return array;int current;for (int i = 0; i < array.length - 1; i++) {current = array[i + 1];int preIndex = i;while (preIndex >= 0 && current < array[preIndex]) {array[preIndex + 1] = array[preIndex];preIndex--;}array[preIndex + 1] = current;}return array;}3.4算法分析最佳情况：T(n) = O(n) 最坏情况：T(n) = O(n2) 平均情况：T(n) = O(n2)4、希尔排序是简单插⼊排序经过改进之后的⼀个更⾼效的版本，也称为缩⼩增量排序，同时该算法是冲破O(n2）的第⼀批算法之⼀。
10个经典的C语言基础算法及代码1.冒泡排序算法冒泡排序是一种简单但效率较低的排序算法，在每一轮遍历中比较相邻的两个元素，如果顺序不正确则交换它们，直到整个数组有序为止。
```cvoid bubbleSort(int arr[], int n)for (int i = 0; i < n-1; i++)for (int j = 0; j < n-1-i; j++)if (arr[j] > arr[j+1])int temp = arr[j];arr[j] = arr[j+1];arr[j+1] = temp;}}}```2.选择排序算法选择排序是一种简单直观的排序算法，它每次从待排序的数组中选择最小（或最大）的元素，并放到已排序的数组末尾。
```cvoid selectionSort(int arr[], int n)for (int i = 0; i < n-1; i++)int min_index = i;for (int j = i+1; j < n; j++)if (arr[j] < arr[min_index])min_index = j;}}int temp = arr[i];arr[i] = arr[min_index];arr[min_index] = temp;}```3.插入排序算法插入排序的基本思想是将数组分为已排序和未排序两部分，每次将未排序的元素插入到已排序的合适位置。
```cvoid insertionSort(int arr[], int n)for (int i = 1; i < n; i++)int key = arr[i];int j = i - 1;while (j >= 0 && arr[j] > key)arr[j+1] = arr[j];j--;}arr[j+1] = key;}```4.快速排序算法快速排序使用分治法的思想，每次选择一个基准元素，将小于基准的元素放到左边，大于基准的元素放到右边，然后递归地对左右两个子数组进行排序。
C语⾔⼋⼤排序算法C语⾔⼋⼤排序算法，附动图和详细代码解释！来源：C语⾔与程序设计、⽵⾬听闲等⼀前⾔如果说各种编程语⾔是程序员的招式，那么数据结构和算法就相当于程序员的内功。
想写出精炼、优秀的代码，不通过不断的锤炼，是很难做到的。
⼆⼋⼤排序算法排序算法作为数据结构的重要部分，系统地学习⼀下是很有必要的。
1、排序的概念排序是计算机内经常进⾏的⼀种操作，其⽬的是将⼀组“⽆序”的记录序列调整为“有序”的记录序列。
排序分为内部排序和外部排序。
若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序。
反之，若参加排序的记录数量很⼤，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。
2、排序分类⼋⼤排序算法均属于内部排序。
如果按照策略来分类，⼤致可分为：交换排序、插⼊排序、选择排序、归并排序和基数排序。
如下图所⽰：3、算法分析1.插⼊排序*直接插⼊排序*希尔排序2.选择排序*简单选择排序*堆排序3.交换排序*冒泡排序*快速排序4.归并排序5.基数排序不稳定排序：简单选择排序，快速排序，希尔排序，堆排序稳定排序：冒泡排序，直接插⼊排序，归并排序，奇数排序1、插⼊排序将第⼀个和第⼆个元素排好序，然后将第3个元素插⼊到已经排好序的元素中，依次类推（插⼊排序最好的情况就是数组已经有序了）因为插⼊排序每次只能操作⼀个元素，效率低。
元素个数N，取奇数k=N/2，将下标差值为k的数分为⼀组（⼀组元素个数看总元素个数决定），在组内构成有序序列，再取k=k/2，将下标差值为k的数分为⼀组，构成有序序列，直到k=1，然后再进⾏直接插⼊排序。
3、简单选择排序选出最⼩的数和第⼀个数交换，再在剩余的数中⼜选择最⼩的和第⼆个数交换，依次类推4、堆排序以升序排序为例，利⽤⼩根堆的性质（堆顶元素最⼩）不断输出最⼩元素，直到堆中没有元素1.构建⼩根堆2.输出堆顶元素3.将堆低元素放⼀个到堆顶，再重新构造成⼩根堆，再输出堆顶元素，以此类推5、冒泡排序改进1：如果某次冒泡不存在数据交换，则说明已经排序好了，可以直接退出排序改进2：头尾进⾏冒泡，每次把最⼤的沉底，最⼩的浮上去，两边往中间靠16、快速排序选择⼀个基准元素，⽐基准元素⼩的放基准元素的前⾯，⽐基准元素⼤的放基准元素的后⾯，这种动作叫分区，每次分区都把⼀个数列分成了两部分，每次分区都使得⼀个数字有序，然后将基准元素前⾯部分和后⾯部分继续分区，⼀直分区直到分区的区间中只有⼀个元素的时候，⼀个元素的序列肯定是有序的嘛，所以最后⼀个升序的序列就完成啦。
排序算法十大经典方法
排序算法是计算机科学中的经典问题之一，它们用于将一组元素按照一定规则排序。
以下是十大经典排序算法：
1. 冒泡排序：比较相邻元素并交换，每一轮将最大的元素移动到最后。
2. 选择排序：每一轮选出未排序部分中最小的元素，并将其放在已排序部分的末尾。
3. 插入排序：将未排序部分的第一个元素插入到已排序部分的合适位置。
4. 希尔排序：改进的插入排序，将数据分组排序，最终合并排序。
5. 归并排序：将序列拆分成子序列，分别排序后合并，递归完成。
6. 快速排序：选定一个基准值，将小于基准值的元素放在左边，大于基准值的元素放在右边，递归排序。
7. 堆排序：将序列构建成一个堆，然后一次将堆顶元素取出并调整堆。
8. 计数排序：统计每个元素出现的次数，再按照元素大小输出。
9. 桶排序：将数据分到一个或多个桶中，对每个桶进行排序，最后输出。
10. 基数排序：按照元素的位数从低到高进行排序，每次排序只考虑一位。
以上是十大经典排序算法，每个算法都有其优缺点和适用场景，选择合适的算法可以提高排序效率。
C语言入门必学—10个经典C语言算法C语言是一种广泛使用的编程语言，具有高效、灵活和易学的特点。
它不仅在软件开发中被广泛应用，也是计算机科学专业的必修课。
在学习C语言的过程中，掌握一些经典的算法是非常重要的。
本文将介绍10个经典C语言算法，帮助读者更好地了解和掌握C语言。
一、冒泡排序算法（Bubble Sort）冒泡排序算法是最简单、也是最经典的排序算法之一。
它通过不断比较相邻的元素并交换位置，将最大（或最小）的元素逐渐“冒泡”到数组的最后（或最前）位置。
二、选择排序算法（Selection Sort）选择排序算法是一种简单但低效的排序算法。
它通过不断选择最小（或最大）的元素，并与未排序部分的第一个元素进行交换，将最小（或最大）的元素逐渐交换到数组的前面（或后面）。
三、插入排序算法（Insertion Sort）插入排序算法是一种简单且高效的排序算法。
它通过将数组分为已排序和未排序两个部分，依次将未排序部分的元素插入到已排序部分的合适位置。
四、快速排序算法（Quick Sort）快速排序算法是一种高效的排序算法。
它采用了分治的思想，通过将数组分为较小和较大两部分，并递归地对两部分进行排序，最终达到整个数组有序的目的。
五、归并排序算法（Merge Sort）归并排序算法是一种高效的排序算法。
它采用了分治的思想，将数组一分为二，递归地对两个子数组进行排序，并将结果合并，最终得到有序的数组。
六、二分查找算法（Binary Search）二分查找算法是一种高效的查找算法。
它通过不断将查找范围折半，根据中间元素与目标值的大小关系，缩小查找范围，最终找到目标值所在的位置。
七、递归算法（Recursive Algorithm）递归算法是一种通过自我调用的方式解决问题的算法。
在C语言中，递归算法常用于解决树的遍历、问题分解等情况。
八、斐波那契数列算法（Fibonacci Sequence）斐波那契数列是一列数字，其中每个数字都是前两个数字的和。
⼗⼤经典排序算法（动图演⽰）0、算法概述0.1 算法分类⼗种常见排序算法可以分为两⼤类：⽐较类排序：通过⽐较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为⾮线性时间⽐较类排序。
⾮⽐较类排序：不通过⽐较来决定元素间的相对次序，它可以突破基于⽐较排序的时间下界，以线性时间运⾏，因此也称为线性时间⾮⽐较类排序。
0.2 算法复杂度0.3 相关概念稳定：如果a原本在b前⾯，⽽a=b，排序之后a仍然在b的前⾯。
不稳定：如果a原本在b的前⾯，⽽a=b，排序之后 a 可能会出现在 b 的后⾯。
时间复杂度：对排序数据的总的操作次数。
反映当n变化时，操作次数呈现什么规律。
空间复杂度：是指算法在计算机内执⾏时所需存储空间的度量，它也是数据规模n的函数。
1、冒泡排序（Bubble Sort）冒泡排序是⼀种简单的排序算法。
它重复地⾛访过要排序的数列，⼀次⽐较两个元素，如果它们的顺序错误就把它们交换过来。
⾛访数列的⼯作是重复地进⾏直到没有再需要交换，也就是说该数列已经排序完成。
这个算法的名字由来是因为越⼩的元素会经由交换慢慢“浮”到数列的顶端。
1.1 算法描述⽐较相邻的元素。
如果第⼀个⽐第⼆个⼤，就交换它们两个；对每⼀对相邻元素作同样的⼯作，从开始第⼀对到结尾的最后⼀对，这样在最后的元素应该会是最⼤的数；针对所有的元素重复以上的步骤，除了最后⼀个；重复步骤1~3，直到排序完成。
1.2 动图演⽰1.3 代码实现function bubbleSort(arr) {var len = arr.length;for (var i = 0; i < len - 1; i++) {for (var j = 0; j < len - 1 - i; j++) {if (arr[j] > arr[j+1]) { // 相邻元素两两对⽐var temp = arr[j+1]; // 元素交换arr[j+1] = arr[j];arr[j] = temp;}}}return arr;}2、选择排序（Selection Sort）选择排序(Selection-sort)是⼀种简单直观的排序算法。
一．七大排序算法基本属性1.稳定性KMP模糊匹配算法二叉树的建立顺序查找：哨兵设置二．七大排序算法（）/jingmoxukong/p/4329079.html1.冒泡排序：冒泡排序是一种交换排序。
什么是交换排序呢？交换排序：两两比较待排序的关键字，并交换不满足次序要求的那对数，直到整个表都满足次序要求为止。
算法思想它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。
走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端，故名。
假设有一个大小为N 的无序序列。
冒泡排序就是要每趟排序过程中通过两两比较，找到第i 个小（大）的元素，将其往上排。
图-冒泡排序示例图以上图为例，演示一下冒泡排序的实际流程：假设有一个无序序列{ 4. 3. 1. 2, 5 }第一趟排序：通过两两比较，找到第一小的数值1 ，将其放在序列的第一位。
第二趟排序：通过两两比较，找到第二小的数值2 ，将其放在序列的第二位。
第三趟排序：通过两两比较，找到第三小的数值3 ，将其放在序列的第三位。
至此，所有元素已经有序，排序结束。
要将以上流程转化为代码，我们需要像机器一样去思考，不然编译器可看不懂。
假设要对一个大小为N 的无序序列进行升序排序（即从小到大）。
(1) 每趟排序过程中需要通过比较找到第i 个小的元素。
所以，我们需要一个外部循环，从数组首端(下标0) 开始，一直扫描到倒数第二个元素（即下标N - 2) ，剩下最后一个元素，必然为最大。
(2) 假设是第i 趟排序，可知，前i-1 个元素已经有序。
现在要找第i 个元素，只需从数组末端开始，扫描到第i 个元素，将它们两两比较即可。
所以，需要一个内部循环，从数组末端开始（下标N - 1），扫描到(下标i + 1)。
核心代码public void bubbleSort(int[] list) {int temp = 0; // 用来交换的临时数// 要遍历的次数for (int i = 0; i < list.length - 1; i++) {// 从后向前依次的比较相邻两个数的大小，遍历一次后，把数组中第i小的数放在第i个位置上for (int j = list.length - 1; j > i; j--) {// 比较相邻的元素，如果前面的数大于后面的数，则交换if (list[j - 1] > list[j]) {temp = list[j - 1];list[j - 1] = list[j];list[j] = temp;}}}}时间复杂度若文件的初始状态是正序的，一趟扫描即可完成排序。
链表排序（冒泡、选择、插⼊、快排、归并、希尔、堆排序）这篇⽂章分析⼀下链表的各种排序⽅法。
以下排序算法的正确性都可以在LeetCode的这⼀题检测。
本⽂⽤到的链表结构如下（排序算法都是传⼊链表头指针作为参数，返回排序后的头指针）struct ListNode {int val;ListNode *next;ListNode(int x) : val(x), next(NULL) {}};插⼊排序（算法中是直接交换节点，时间复杂度O（n^2）,空间复杂度O（1））class Solution {public:ListNode *insertionSortList(ListNode *head) {// IMPORTANT: Please reset any member data you declared, as// the same Solution instance will be reused for each test case.if(head == NULL || head->next == NULL)return head;ListNode *p = head->next, *pstart = new ListNode(0), *pend = head;pstart->next = head; //为了操作⽅便，添加⼀个头结点while(p != NULL){ListNode *tmp = pstart->next, *pre = pstart;while(tmp != p && p->val >= tmp->val) //找到插⼊位置{tmp = tmp->next; pre = pre->next;}if(tmp == p)pend = p;else{pend->next = p->next;p->next = tmp;pre->next = p;}p = pend->next;}head = pstart->next;delete pstart;return head;}};选择排序（算法中只是交换节点的val值，时间复杂度O（n^2）,空间复杂度O（1））class Solution {public:ListNode *selectSortList(ListNode *head) {// IMPORTANT: Please reset any member data you declared, as// the same Solution instance will be reused for each test case.//选择排序if(head == NULL || head->next == NULL)return head;ListNode *pstart = new ListNode(0);pstart->next = head; //为了操作⽅便，添加⼀个头结点ListNode*sortedTail = pstart;//指向已排好序的部分的尾部while(sortedTail->next != NULL){ListNode*minNode = sortedTail->next, *p = sortedTail->next->next;//寻找未排序部分的最⼩节点while(p != NULL){if(p->val < minNode->val)minNode = p;p = p->next;}swap(minNode->val, sortedTail->next->val);sortedTail = sortedTail->next;}head = pstart->next;delete pstart;return head;}};快速排序1（算法只交换节点的val值，平均时间复杂度O（nlogn）,不考虑递归栈空间的话空间复杂度是O（1））这⾥的partition我们参考(选取第⼀个元素作为枢纽元的版本，因为链表选择最后⼀元素需要遍历⼀遍)，具体可以参考这⾥我们还需要注意的⼀点是数组的partition两个参数分别代表数组的起始位置，两边都是闭区间，这样在排序的主函数中：void quicksort(vector<int>&arr, int low, int high){if(low < high){int middle = mypartition(arr, low, high);quicksort(arr, low, middle-1);quicksort(arr, middle+1, high);}}对左边⼦数组排序时，⼦数组右边界是middle-1，如果链表也按这种两边都是闭区间的话，找到分割后枢纽元middle，找到middle-1还得再次遍历数组，因此链表的partition采⽤前闭后开的区间（这样排序主函数也需要前闭后开区间），这样就可以避免上述问题class Solution {public:ListNode *quickSortList(ListNode *head) {// IMPORTANT: Please reset any member data you declared, as// the same Solution instance will be reused for each test case.//链表快速排序if(head == NULL || head->next == NULL)return head;qsortList(head, NULL);return head;}void qsortList(ListNode*head, ListNode*tail){//链表范围是[low, high)if(head != tail && head->next != tail){ListNode* mid = partitionList(head, tail);qsortList(head, mid);qsortList(mid->next, tail);}}ListNode* partitionList(ListNode*low, ListNode*high){//链表范围是[low, high)int key = low->val;ListNode* loc = low;for(ListNode*i = low->next; i != high; i = i->next)if(i->val < key){loc = loc->next;swap(i->val, loc->val);}swap(loc->val, low->val);return loc;}};快速排序2（算法交换链表节点，平均时间复杂度O（nlogn）,不考虑递归栈空间的话空间复杂度是O（1））这⾥的partition，我们选取第⼀个节点作为枢纽元，然后把⼩于枢纽的节点放到⼀个链中，把不⼩于枢纽的及节点放到另⼀个链中，最后把两条链以及枢纽连接成⼀条链。
十大经典排序法
1. 冒泡排序（Bubble Sort）：通过不断比较相邻元素并交换位置来排序，每一轮将最大的元素冒泡到最后。
2. 选择排序（Selection Sort）：通过找到当前未排序部分的最小元素，将其放置到已排序部分的末尾，逐步构建有序序列。
3. 插入排序（Insertion Sort）：将未排序元素逐个插入到已排序部分的正确位置，从而逐步构建有序序列。
4. 希尔排序（Shell Sort）：是插入排序的改进版本，通过比较相隔一定间隔的元素进行排序，逐渐缩小间隔直至为1。
5. 归并排序（Merge Sort）：采用分治策略，将待排序序列不断拆分为子序列，然后将子序列排序并合并得到最终有序序列。
6. 快速排序（Quick Sort）：也是采用分治策略，通过选择一个基准元素将序列划分为左右两部分，分别对两部分进行排序。
7. 堆排序（Heap Sort）：利用二叉堆的性质来进行排序，将待排序元素构建成最大（最小）堆，然后依次取出堆顶元素并调整堆结构。
8. 计数排序（Counting Sort）：适用于元素值范围较小的情况，通过统计元素出现的次数，然后根据统计结果得到有序序列。
9. 桶排序（Bucket Sort）：将元素根据大小分配到不同的桶中，每个桶内部再分别进行排序，最后将各个桶中的元素合并得到有序序列。
10. 基数排序（Radix Sort）：将待排序元素按照位数进行排序，先按个位排序，再按十位排序，依此类推，直到最高位排序完成。
⼗⼤排序算法算法之排序排序算法基本上是我们⽆论是在项⽬中还是在⾯试中都会遇到的问题，加上最近在看《算法》这本书，所以就准备好好的将排序算法整理⼀下。
所有排序算法都是基于 Java 实现，为了简单，只使⽤了int类型，从⼩到⼤排序基本排序⾼效的排序各⼤排序的时间测试如何选择排序排序之基本排序算法准备阶段：有⼀个交换位置的函数exc/*** 交换a数组中i和j的位置* @param a 需要交换的数组* @param i 位置* @param j 位置*/public static void exc(int a[],int i,int j){// 当他们相等的时候就没必要进⾏交换if(a[i] != a[j]){a[i] ^= a[j];a[j] ^= a[i];a[i] ^= a[j];}}基本排序算法主要是分为插⼊排序，选择排序，冒泡排序和梳排序。
选择排序原理：选择排序的原理很简单，就是从需要排序的数据中选择最⼩的（从⼩到⼤排序），然后放在第⼀个，选择第⼆⼩的放在第⼆个……代码：/*** 选择排序* @param a 进⾏排序的数组*/public static int[] selectionSort(int a[]){int min;for(int i=0;i<a.length;i++){min = i;// 这个for循环是为了找出最⼩的值for (int j = i+1; j < a.length; j++) {if(a[min]>a[j]){min = j;}}/** 如果第⼀个取出的元素不是最⼩值，就进⾏交换* 意思就是：如果取出的元素就是最⼩值，那么就没有必要进⾏交换了 */if(min != i){// 进⾏交换exc(a, i, min);}}return a;}选择排序的动画演⽰img假如数组的长度是N，则时间复杂度：进⾏⽐较的次数：(N-1)+(N-2)+……+1 = N(N-1)/2进⾏交换的次数：N特点：（稳定）1. 运⾏时间与输⼊⽆关。
白话经典算法系列（转载）原文作者：MoreWindows目录白话经典算法系列（转载） (1)白话经典算法系列之一冒泡排序的三种实现 (2)白话经典算法系列之二直接插入排序的三种实现 (4)白话经典算法系列之三希尔排序的实现 (6)白话经典算法系列之四直接选择排序及交换二个数据的正确实现 (9)白话经典算法系列之五归并排序的实现 (11)白话经典算法系列之六快速排序快速搞定 (15)白话经典算法系列之七堆与堆排序 (19)二叉堆的定义 (19)堆的存储 (19)堆的操作——插入删除 (20)堆的插入 (21)堆的删除 (21)堆化数组 (22)堆排序 (24)转载请标明出处，原文地址：/morewindows/archive/2011/08/22/2149612.html (24)白话经典算法系列之一冒泡排序的三种实现冒泡排序是非常容易理解和实现，以从小到大排序举例：设数组长度为N。
1．比较相邻的前后二个数据，如果前面数据大于后面的数据，就将二个数据交换。
2．这样对数组的第0个数据到N-1个数据进行一次遍历后，最大的一个数据就“沉”到数组第N-1个位置。
3．N=N-1，如果N不为0就重复前面二步，否则排序完成。
按照定义很容易写出代码：//冒泡排序1void BubbleSort1(int a[], int n){int i, j;for (i = 0; i < n; i++)for (j = 1; j < n - i; j++)if (a[j - 1] > a[j])Swap(a[j - 1], a[j]);}下面对其进行优化，设置一个标志，如果这一趟发生了交换，则为true，否则为false。
明显如果有一趟没有发生交换，说明排序已经完成。
//冒泡排序2void BubbleSort2(int a[], int n){int j, k;bool flag;k = n;flag = true;while (flag){flag = false;for (j = 1; j < k; j++)if (a[j - 1] > a[j]){Swap(a[j - 1], a[j]);flag = true;}k--;}}再做进一步的优化。
如果有100个数的数组，仅前面10个无序，后面90个都已排好序且都大于前面10个数字，那么在第一趟遍历后，最后发生交换的位置必定小于10，且这个位置之后的数据必定已经有序了，记录下这位置，第二次只要从数组头部遍历到这个位置就可以了。
//冒泡排序3void BubbleSort3(int a[], int n){int j, k;int flag;flag = n;while (flag > 0){k = flag;flag = 0;for (j = 1; j < k; j++)if (a[j - 1] > a[j]){Swap(a[j - 1], a[j]);flag = j;}}}冒泡排序毕竟是一种效率低下的排序方法，在数据规模很小时，可以采用。
数据规模比较大时，最好用其它排序方法。
白话经典算法系列之二直接插入排序的三种实现直接插入排序(Insertion Sort)的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。
设数组为a[0…n-1]。
1.初始时，a[0]自成1个有序区，无序区为a[1..n-1]。
令i=12.将a[i]并入当前的有序区a[0…i-1]中形成a[0…i]的有序区间。
3.i++并重复第二步直到i==n-1。
排序完成。
下面给出严格按照定义书写的代码（由小到大排序）：void Insertsort1(int a[], int n){int i, j, k;for (i = 1; i < n; i++){//为a[i]在前面的a[0...i-1]有序区间中找一个合适的位置for (j = i - 1; j >= 0; j--)if (a[j] < a[i])break;//如找到了一个合适的位置if (j != i - 1){//将比a[i]大的数据向后移int temp = a[i];for (k = i - 1; k > j; k--)a[k + 1] = a[k];//将a[i]放到正确位置上a[k + 1] = temp;}}}这样的代码太长了，不够清晰。
现在进行一下改写，将搜索和数据后移这二个步骤合并。
即每次a[i]先和前面一个数据a[i-1]比较，如果a[i] > a[i-1]说明a[0…i]也是有序的，无须调整。
否则就令j=i-1,temp=a[i]。
然后一边将数据a[j]向后移动一边向前搜索，当有数据a[j]<a[i]时停止并将temp放到a[j + 1]处。
void Insertsort2(int a[], int n){int i, j;for (i = 1; i < n; i++)if (a[i] < a[i - 1]){int temp = a[i];for (j = i - 1; j >= 0 && a[j] > temp; j--)a[j + 1] = a[j];a[j + 1] = temp;}}再对将a[j]插入到前面a[0…j-1]的有序区间所用的方法进行改写，用数据交换代替数据后移。
如果a[j]前一个数据a[j-1] > a[j]，就交换a[j]和a[j-1]，再j--直到a[j-1] <= a[j]。
这样也可以实现将一个新数据新并入到有序区间。
void Insertsort3(int a[], int n){int i, j;for (i = 1; i < n; i++)for (j = i - 1; j >= 0 && a[j] > a[j + 1]; j--)Swap(a[j], a[j + 1]);}白话经典算法系列之三希尔排序的实现希尔排序的实质就是分组插入排序，该方法又称缩小增量排序，因DL．Shell于1959年提出而得名。
该方法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。
因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。
以n=10的一个数组49, 38, 65, 97, 26, 13, 27, 49, 55, 4为例第一次gap = 10 / 2 = 549 38 65 97 26 13 27 49 55 41A 1B2A 2B3A 3B4A 4B5A 5B1A,1B，2A,2B等为分组标记，数字相同的表示在同一组，大写字母表示是该组的第几个元素，每次对同一组的数据进行直接插入排序。
即分成了五组(49, 13) (38, 27) (65, 49) (97, 55) (26, 4)这样每组排序后就变成了(13, 49) (27, 38) (49, 65) (55, 97) (4, 26)，下同。
第二次gap = 5 / 2 = 2排序后13 27 49 55 4 49 38 65 97 261A 1B 1C 1D 1E2A 2B 2C 2D 2E第三次gap = 2 / 2 = 14 26 13 27 38 49 49 55 97 651A 1B 1C 1D 1E 1F 1G 1H 1I 1J第四次gap = 1 / 2 = 0 排序完成得到数组：4 13 26 27 38 49 49 55 65 97下面给出严格按照定义来写的希尔排序void shellsort1(int a[], int n){int i, j, gap;for (gap = n / 2; gap > 0; gap /= 2) //步长for (i = 0; i < gap; i++) //按组排序{for (j = i + gap; j < n; j += gap){if (a[j] < a[j - gap]){int temp = a[j];int k = j - gap;while (k >= 0 && a[k] > temp){a[k + gap] = a[k];k -= gap;}a[k + gap] = temp;}}}}很明显，上面的shellsort1代码虽然对直观的理解希尔排序有帮助，但代码量太大了，不够简洁清晰。
因此进行下改进和优化，以第二次排序为例，原来是每次从1A到1E，从2A到2E，可以改成从1B开始，先和1A比较，然后取2B与2A比较，再取1C与前面自己组内的数据比较…….。
这种每次从数组第gap个元素开始，每个元素与自己组内的数据进行直接插入排序显然也是正确的。
void shellsort2(int a[], int n){int j, gap;for (gap = n / 2; gap > 0; gap /= 2)for (j = gap; j < n; j++) //从数组第gap个元素开始if (a[j] < a[j - gap]) //每个元素与自己组内的数据进行直接插入排序{int temp = a[j];int k = j - gap;while (k >= 0 && a[k] > temp){a[k + gap] = a[k];k -= gap;}a[k + gap] = temp;}}再将直接插入排序部分用白话经典算法系列之二直接插入排序的三种实现中直接插入排序的第三种方法来改写下：void shellsort3(int a[], int n){int i, j, gap;for (gap = n / 2; gap > 0; gap /= 2)for (i = gap; i < n; i++)for (j = i - gap; j >= 0 && a[j] > a[j + gap]; j -= gap)Swap(a[j], a[j + gap]);}这样代码就变得非常简洁了。
附注：上面希尔排序的步长选择都是从n/2开始，每次再减半，直到最后为1。
其实也可以有另外的更高效的步长选择，如果读者有兴趣了解，请参阅维基百科上对希尔排序步长的说明：/wiki/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8 F白话经典算法系列之四直接选择排序及交换二个数据的正确实现直接选择排序和直接插入排序类似，都将数据分为有序区和无序区，所不同的是直接播放排序是将无序区的第一个元素直接插入到有序区以形成一个更大的有序区，而直接选择排序是从无序区选一个最小的元素直接放到有序区的最后。
