几种排序方法
这两天复习了一下排序方面的知识，现将目前比较常见的整理一下。 选择排序选择排序的思想是首先先找到序列中最大元素并将它与序列中最后一个元素交换，然后找下一个最大元素并与倒数第二个元素交换，依次类推。此排序很简单，这不做多说，代码实现如下：View Code插入排序算法流程： 1. 从第一个元素开始，该元素可以认为已经被排序 2. 取出下一个元素，在已经排序的元素序列中从后向前扫描 3. 如果该元素（已排序）大于新元素，将该元素移到下一位置 4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置 5. 将新元素插入到下一位置中 6. 重复步骤2View Code冒泡排序依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序。 View Code合并排序 在介绍合并排序之前，首先介绍下递归设计的技术，称为分治法。分治法的核心思想是：当问题比较小时，直接解决。当问题比较大时，将问题分为两个较小的子问题，每个子问题约为原来的一半。使用递归调用解决每个子问题。递归调用结束后，常常需要额外的处理，将较小的问题的结果合并，得到较大的问题的答案。 合并排序算法在接近数组中间的位置划分数组，然后使用递归运算对两个一半元素构成的数组进行排序，最后将两个子数组进行合并，形成一个新的已排好序的数组。 代码如下：View Code快速排序 快速排序与合并排序有着很多相似性。将要排序的数组分成两个子数组，通过两次递归调用分别对两个数组进行排序，再将已经排好序的两个数组合并成一个独立的有序数组。但是，将数组一分为二的做法比合并排序中使用的简单方法复杂的多。它需要将所有小于或者等于基准元素的元素放置到基准元素前面的位置，将大于基准的元素放置到基准后面的位置。
几种常见的排序（冒泡、选择、插入、希尔、堆排序）
内排序:是在排序整个过程中,待排序的所有记录全部被放置在内存中;
外排序:由于排序的记录个数太多,不不能同时放置在内存,整个排序过程需要在内外存 之间多次交换数据才能进⾏
1、顺序表结构
2、数据交换函数
3、数据打印
冒泡排序(Bubble Sort) 一种交换排序,它的基本思想就是: 两两⽐比较相邻的记录的关键字,如果 反序则交换,直到没有反序的记录为⽌.
也可以反过来，每次都把最大的值放到末尾。
简单排序算法(Simple Selection Sort) 就是通过n-i次关键词比较,从n-i+1个记录中找出关键 字最小的记录,并和第i(1<=i<=n) 个记录进行交换.
总结一句话就是(划重点)：从第一个位置开始比较，找出最小的，和第一个位置互换，开始下一轮。
（1）冒泡排序是比较相邻位置的两个数，而选择排序是按顺序比较，找最大值或者最小值；
（2）冒泡排序每一轮比较后，位置不对都需要换位置，选择排序每一轮比较都只需要换一次位置；
（3）冒泡排序是通过数去找位置，选择排序是给定位置去找数；
冒泡排序优缺点：优点:比较简单，空间复杂度较低，是稳定的；
缺点:时间复杂度太高，效率慢；
选择排序优缺点：优点：一轮比较只需要换一次位置；
缺点：效率慢，不稳定（举个例子5，8，5，2，9 我们知道第一遍选择第一个元素5会和2交换，那么原序列中2个5的相对位置前后顺序就破坏了）。
直接插入排序算法(Stright Insertion Sort)的基本操作是将一个记录插入到已经排好序的有序表 中,从而得到一个新的,记录数增1的有序表;
步骤1、将数据插入到有序表中与前一个比较，如果大于则不改变位置
2、如果插入数据小于前一个数据，则前面大的数据依次往后移动，然后找到合适位置插入该数据。
空间复杂度: O(1) 解读:在直接插⼊入排序中只使⽤用了了i,j,temp这三个辅助元素，与问题规模⽆无关，空间复杂度为O(1)
时间复杂度: O(n2)
希尔排序思想: 希尔排序是把记录按下标的一定增量分组，对每组使用直接插⼊排序算法排 序;随着增量逐渐减少，每组包含的关键词越来越多，当增量减⾄1时，整个序列恰被分成 一组，算法便终止.
其实就是分治法升级版的插入排序，又称为缩小增量排序。我们不断减半增量，直到增量为1时，退化为普通插入排序。
希尔排序通过增量进行了分组(分治)，比较的是L->r[j-increment]和L->[j]，跨度是increment，如果摸到的是较小的牌，只需要移动1次，而插入排序需要移动increment次。
也就是说希尔排序的优势是，能让较小的牌更容易来到数组的前面部分，节约了移动次数。
需要注意的是：
由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以希尔排序是不稳定的。
每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆。
或者
每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
如下图1为大顶堆：
下图为小顶堆：
我们用简单的公式来描述一下堆的定义就是：
大顶堆： arr[i] >= arr[2i] && arr[i] >= arr[2i+1]
小顶堆： arr[i] <= arr[2i] && arr[i] <= arr[2i+1]
1、用待排序序列构造一个大顶堆。
2、将其与末尾元素进行交换，此时末尾就为最大值。
3、然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。
4、如此反复执行，便能得到一个有序序列了。
我们可以发现其实堆排序还是一种选择排序，用一句话概括思想：
利用堆结构特性，不断选出最大值，放到最后。
归并排序(Merging Sort) 就是利利⽤用归并的思想实现排序⽅方法. 它的原理理是假设初始序 列列含有n个记录,则可以看成n个有序的⼦子序列列. 每个⼦子序列列的⻓长度为1,然后两两合并.得 到[n/2]个⻓长度为2或1的有序⼦子序列列, 再两两归并. ......如此重复,直到得到⼀一个⻓长度为n 的有序序列列为此. 这种排序⽅方法称为2路路归并排序
归并排序是利用归并的思想实现的排序方法，该算法采用经典的分治策略。
将问题分成一些小的问题然后递归求解，而治的阶段则将分的阶段得到的各答案修补在一起。
进行合并时，我们需要一个额外的数组来进行辅助排序，再回填回原数组。
//6归并排序
首先设定一个分界值，通过该分界值将数组分成左右两部分。
将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。
此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。
左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。