算法学习一之常见的七大排序算法
算法之排序
十三个经典算法研究与总结、目录+索引
http://blog.csdn.net/v_july_v/article/details/6305212
排序的一些概念
稳定性和不稳定性：关键字相等的记录在排序情况不唯一。
内排序和外排序：简单来说前者的操作都是在内存中，后者数据太多，存在于外部存储设备的交互操作。
一般我们说的的算法都是值指的内排序。
对于排序的分类可能有好几种：
一般按操作方式和思想可分为：交换，插入，选择，合并等。
也有按计算复杂度的来分的，O（n^2）简单排序（冒泡，简单选折，直接插入）和改进排序算法 （希尔排序，堆排序，归并排序，快速排序）
这边主要学习几个常用的算法，也是最近一舍友去面试时说，现在问的算法好多。
然后这礼拜断断续续的从周一到周四，抽了点时间温故而知新，顺便也保持做笔记的好习惯。（我这是有多闲啊！）
在最基本的排序算法中，快排是出境率最高的。也是这些算法中相对来说效率最优异的。
我顺便就再去看了遍这几个算法的实现。因为可能说你了解是了解，转化成代码时，还真有点难度。我就当复习复习
实现语言我用的是java，因为比较熟，但是其真正要写得优雅和简洁，那就得c来写。并且在目前大部分数据结构书上也都是C来实现教学的。
我这用java，权当走一遍思路流程。
一：简单排序
这里主要包括3种：
1.冒泡排序。操作思想是：不断两两比较和交换。
也是最简单的排序。
简单排序的思路很简单，依次比较相邻的两个数，将小数放在前面，大数放在后面。2层循环
内层循环一次后比较相邻的哪个大小，外层循环一次后，确定了末尾的元素为最大值。
因此下次内层训话后可以不用在比较最末尾的两元素的比较。
整体的比较次数即为：（1+n）*n/2 复杂度为O(n^2)。
基本实现Java代码：
[java] view plaincopy
private static int[] BubbleSort(int[] nums){
int count = 0;
for(int i = 0 ; i < nums.length-1; i++){
for(int j = 0; j < nums.length-i-1;j++){
count++;
if(nums[j] > nums [j+1]){
int temp = nums[j];
nums[j] = nums[j+1];
nums[j+1] = temp;
}
}
}
System.out.println("执行比较次数："+count);
return nums;
}
冒泡的一点优化：
比如我有一个数组是部分有序的 {3,2,5,7,8,9}
那么比较外层i = 0的时候 内循环结束后其实整个序列就是排序完了。但是按上面的逻辑，外层循环又执行了i++，即i =1，在跳进内层循环比较。
一圈比较下来后其实根本没有发生元素交换，因为他本身已经是有序的了。然后紧接着i =2,3,4.。。。其实此时就完全可以退出整个循环了。
因此，我们增加一个标志位，对以上代码做一点点改进
[java] view plaincopy
private static int[] BubbleSort(int[] nums) {
int count = 0;
boolean flag = true;
for (int i = 0; i < nums.length - 1 &&flag ; i++) {//外层训话
flag = false;
for (int j = 0; j < nums.length - i - 1; j++) {//内层循环
count++;
if (nums[j] > nums[j + 1]) {//比较大小，大的放后面，小的放前面
int temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp;
flag = true;
}
}
}
System.out.println("执行比较次数：" + count);
return nums;
}
冒泡法的变种：鸡尾酒排序。基本的思路是，先从左端升序，再从右端降序。
[java] view plaincopy
private static int[] cockTail(int[] nums) {
int count = 0;
boolean flag = true;
int left = 0;
int right = nums.length-1;
while(flag){
flag = false;
for(int i = left; i<right;i++){
if (nums[i] > nums[i + 1]) {
int temp = nums[i];
nums[i] = nums[i + 1];
nums[i + 1] = temp;
flag = true;
}
count++;
}
right --;
for(int i = right; i>left;i--){
if (nums[i-1] > nums[i]) {
int temp = nums[i];
nums[i] = nums[i - 1];
nums[i - 1] = temp;
flag = true;
}
count++;
}
left ++;
}
System.out.println("执行比较次数：" + count);
return nums;
}
但是我测试了几次，鸡尾酒排序在查找的次数根本对传统的冒泡没有什么提升，但只是说因为随着left和right的缩小，元素在交换时移动的位置移动次数上可能会有一点减少。
而查了下资料还有一种是双向冒泡，基本实现和鸡尾酒这个很像。
总体来说冒泡排序就是最基本的一种排序方式。百度百科还表示有一种局部冒泡。但对于这样的一种排序，传统意义上的深入不如来的对新的排序研究来的有价值，当然，喜欢研究的朋友可以更深入的了解。我这边只是做下记录，以及自己学习的笔记。
2.简单选择排序
操作思想是在每一次扫描时选取关键字最小的记录作为最左端的元素。
[java] view plaincopy
private static void SimpleSelectSort(int[]nums){
for(int i = 0; i < nums.length; i++){//外层扫面控制
int min = i;//用来记录值最小的下标，默认假设第数组第一个元素为最小。
for(int j = i; j < nums.length ; j++){
if(nums[j] < nums[min]){//找出逼min下标中元素还小的值的下标
min = j;//保持min始终为最小元素的小标
}
}
if(i!=min){//一趟扫描结束后判断是否找出了最小的值，如果有的话就交换，将这个最小值移动到此次扫描数据的最前端
int temp = nums[i];
nums[i] = nums[min];
nums[min] = temp;
}
}
}
选择排序相对于了冒泡来说，在数据比较次数上其实没有不同，但是相对于减少了每次比较后若数据需要交换而带来的数据的移动操作，选择排序记录了要移动的下标，说白了，就是先记录下来最后做选择性的移动。总体来说可能比冒泡有一点的提升。
3.直接插入排序
[java] view plaincopy
private static void InsertSort(int[] nums) {
for (int i = 1; i < nums.length; i++) {// 外层对无序列表的扫描
if (nums[i] < nums[i - 1]) {
int temp = nums[i];// 保存该点的值，等会要将该值插入适当位置
int j = i - 1;
// while(j >= 0 && temp < nums[j]){
// nums[j + 1] = nums[j];
// j--;
// }
for (; j >= 0 && temp < nums[j]; j--) {// 往后移 tips此处千万不要 是nums[i] < nums[j]来比较，
//因为nums[i]这个值在一次移位后就被覆盖了，因此也为什么要用temp来保存这个值的原因
nums[j + 1] = nums[j];// 数组往后移
}
nums[j + 1] = temp;
}
}
}
整体来说，对于插入排序，数据的比较和交换的平均次数都是 n^2/2.
二：改进的算法
4.希尔排序.
排序思想：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。（百度百科）
希尔排序是插入排序的一种改进。
[java] view plaincopy
private static void shellSort(int[] nums){
int increment = nums.length;//增量
while(increment >1){
increment = increment/2 ;//增量计算
//一下基本同插入排序,只是直接插入排序我们比较时是增量是1，shell排序设置了一个自己的增量
for(int i = increment; i<nums.length;i++){
if(nums[i] < nums[i-increment]){
int temp = nums[i];
int j = i - increment;
for(;j >=0 && temp < nums[j];j-=increment ){
nums[j+increment] = nums[j];
}
nums[j+increment] = temp;
}
}
}
}
5.堆排序。
定义：“堆”定义
n个关键字序列Kl，K2，…，Kn称为（Heap），当且仅当该序列满足如下性质（简称为堆性质）：
(1)ki<=k(2i）且ki<=k(2i+1)(1≤i≤ n），当然，这是小根堆，大根堆则换成>=号。//k(i）相当于二叉树的非叶结点，K(2i）则是左孩子，k(2i+1）是右孩子
若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：
树中任一非叶结点的关键字均不大于（或不小于）其左右孩子（若存在）结点的关键字。
思想：堆排序是选择排序的一种改进。选择排序的时，我们说是分为有序区和无序区（这边我们升序排，有序区在左边）。对数组排序扫描时第一遍
nums【0,n】所有的比较一边后选取最小的值放在坐标0这个位置，然后第二趟扫描 nums【1，n】，同样的选取最小值放在1位置。然后和我们可以知道，在第,二次对数组nums【1，n】扫描比较时，有很多比较其实在前面第一趟中已经做过，但是没有保存比较记录。因此选用树形的结构来保存。
堆排序的具体步骤：
第一步：将数组构造成堆（这边我们以大根堆来举例）
第二步：其实是第一步的深入，在构造大根堆时，我们根据二叉树特点可知我们可以从最后一个非叶子节点，即节点i = [n/2]，开始扫描比较i节点和其子节点得到大小，如果子节点中大那个值比i节点大，则交换他们的位置。（tips注意点，此刻我们可能觉得i点和他的子节点对于大根堆的定义满足了，这边为了方便我们把这个算作一个事件。i节点事件后满足了大根堆定义。那么继续的i--。）然后操作到树的比较上面几层时（准确的说就是某个节点
j，处理完事件后，产生了节点交换，这时的他的一个子节点改变了，这个子节点非叶子节点，即，把他也拥有子节点，因为j节点的数据于其子节点child交换后，child节点和他的子节点的大根堆结构被破坏了。）看完括号里的注意事项，你应该知道某个节点 j在处理完节点事件后（即发生了数据交换）于j节点发生交换的子节点child拥有子节点（即 child * 2 +1>= n），则需要对child节点事件进行堆的重构。(感觉有点递归的意思了，而且本来树这结构就很容易让人想到递归这概念)。
第三步：第二步后，一棵大根堆就构造完了，此时根元素为最大值，将根元素和大根堆的最后一个元素交换。即，将最大值移动到有序区的最左端，带排序区的最右端。（数组的右端为有序）。
第四步：第三步结束后，则是类似于第二步的节点数据交换事件后的意思是差不多的，即，此刻原本根根节点的这个大根堆结构可能被破换了，那就是重构大根堆了（当然，此时构造大根堆的数组是nums【0，n-1】，而非nums【0，n-1】.。意思大家应该知道。
第五步：第四步结束后对于nums【0，n-1】构建完大堆树，重复第三部，将根元素和当前大根堆最后一个元素，即nums【n-1】互换，重复第四步。
n-1个循环后，排序结束。
时间复杂度分析：将待排序数组构造成大根堆的算法复杂级应该是在 nlogn（n/2个循环，循环里怎么里面是一个二叉树（这个怎么说呢？反正觉得有点二分的感觉。）抱歉我贫乏的专业词汇。假设我们把一个节点事件算法复杂度看成是一个O（1）级。那么最极端或是笼统的算，节点j在每一个节点事件操作后，都需要重构，再极端点的假设说操作的这个节点为根节点，那么要操作的时间级其实就是这颗树的深度 logn,当然这事最极端的想法，其实当节点为 j =【n/2】以及和这个节点在同一层的其他节点事件其实都是
O（1）），因此推测算法复杂级为 nlogn。(当然我这个不是专业的，只是个人的一点理解和认知)。
同理的可以理解后边的交换和重构算法级别还是在 nlogn，最后可得出为 n * logn。
实现代码;
[java] view plaincopy
private static void HeapSort(int[] nums){
int n = nums.length;
//step1：序列构建成大根堆
for(int i = (n-1)/2 ;i >= 0; i--){
//即对每个节点和其子节点的大根堆构造
HeapAdjust(nums, i, n);
}
//step2：遍历最大元素移动到末端
for(int i = n-1 ;i >0; i--){
int temp = nums[i];
nums[i] =nums[0];
nums[0] = temp;
//step3：重构
HeapAdjust(nums, 0, i);
}
}
/**
* 构建大根堆
* @param nums
* @param node
* @param length
*/
private static void HeapAdjust(int[] nums, int node, int length) {
if ((node*2+1) <=length-1) {// 保证该节点为非叶子节点，因为叶子节点就没意义了
int child = node * 2 + 1;//字节点坐标，主要是交换完后需要以该child为节点判断以及调整大根堆
if (child + 1 <= length-1) {//如果有有右子树
if (nums[child + 1] > nums[child]) {
child++;//判断后如果右子树大于左子树，child++，即等会要操作的是左子树节点
}
}
if(nums[node]< nums[child]){//大的子树与node比较
//交换
int temp = nums[node];
nums[node] =nums[child];
nums[child] = temp;
//再次重构
HeapAdjust(nums, child, length);
}
}
}
6.归并排序
概念：归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
思想：分治
归并算法是效率仅次于快排，并且稳定的排序。
在算法过程中需要申请附加的存储空间。
实现步骤：
首先我们要明白本身我们排序的是对于的是一个序列。对于要归并来说，首先要将该序列拆分成两个子序列，两个子序列各自排序成有序的，这就有又涉及到每个子序列的排序了，此刻我们若把一个子序列排序，不就又回到最前面的了么？这就是分治和递归的一种实现。
一：序列排序，先将序列分割成两个有序的子序列。然后执行归并算法
二：在一种将一个无需序列分割中两个子序列后，要执行归并，则要先对每个子序列进行排序，即，对方法一进行递归调用。
三：对于一个递归函数，则必须涉及到函数的结束，即当一个序列元素个数为1时，跳出递归
以下是归并算法的递归实现：
[java] view plaincopy
private static void MergingSort(int [] nums,int head,int tail){
int mid;
if(head >= tail)
return;
//while(head < tail){
//切分子序列，使之为有序子序列
mid = (tail + head)/2;
MergingSort(nums,head,mid);
MergingSort(nums, mid+1, tail);
//归并
Merging(nums, head, mid, tail);
//}
}
private static void Merging(int[] nums, int head, int mid, int tail) {
int[] temp = new int[tail-head+1];// 申请额外空间
int low = head;
int high = tail;
int j = mid + 1;
int p = 0;
//两个子序列都非空
while (head <= mid && j <= tail) {
if (nums[head] > nums[j]) {
temp[p++] = nums[j++];
} else {
temp[p++] = nums[head++];
}
}
//第一个子序列非空，将其中剩余的元素复制到temp中
while (head <= mid) {//
temp[p++] = nums[head++];
}
//第二个子序列非空，将其中剩余的元素复制到temp中
while (j <= tail) {//
temp[p++] = nums[j++];
}
//将缓存中的刷到归并序列中
for(int q=0, t =low ;t<=high;q++,t++){
nums[t]=temp[q];//归并完成后将结果复制回R[low..high]
} //Merge
}
注意点：上面我注释掉的while循环，这个真的是比较郁闷的，理论上来说这么while可行的，但是我测试后，发现跳不出while循环了，因为每次执行完
//归并
Merging(nums, head, mid, tail);
后while判断还是成立的，网上查了下资料，基本都也是这么写。可能因为代码我是按自己的思路书写的，诸侯将循环控制改成if来控制问题倒是解决了。
更多规范代码（比如C和c++）请参考规范文档。
以上是用递归实现的，下面以一个非递归实现的归并。其实思路是差不多的。
在上面我们是先思考将要排序序列分割成一个个子序列，然后再执行归并操作。然后整个形势刚好可以用递归实现，但是，递归来说，在代码的可读性和思路上能说比较好理解，但是递归的每次调用本身的创建副本，如果递归层数太深，内存资源是比较高的。
因此我们也可以转个思路，比如在一开始我们将该待排序序列分成每个子序列程度为1的多个子序列，然后将相邻的两个子序列执行归并排序。
[java] view plaincopy
private static void MergingSort2(int[] nums) {
int length = nums.length;
for (int n = 1; n < nums.length; n *= 2) {// 做logn 趟归并
int i;
for (i = 0; i + 2 * n - 1 <= length-1; i = i + 2 * n) {
Merging(nums, i, i + n - 1, i + 2 * n - 1);// 归并长度为length的两个相邻子文件
}
if (i + n - 1 < nums.length-1) // 尚有两个子文件，其中后一个长度小于length
Merging(nums, i, i + n - 1, nums.length-1); // 归并最后两个子文件
}
}
private static void Merging(int[] nums, int head, int mid, int tail) {
int[] temp = new int[tail-head+1];// 申请额外空间
int low = head;
int high = tail;
int j = mid + 1;
int p = 0;
//两个子序列都非空
while (head <= mid && j <= tail) {
if (nums[head] > nums[j]) {
temp[p++] = nums[j++];
} else {
temp[p++] = nums[head++];
}
}
//第一个子序列非空，将其中剩余的元素复制到temp中
while (head <= mid) {//
temp[p++] = nums[head++];
}
//第二个子序列非空，将其中剩余的元素复制到temp中
while (j <= tail) {//
temp[p++] = nums[j++];
}
//将缓存中的刷到归并序列中
for(int q=0, t =low ;t<=high;q++,t++){
nums[t]=temp[q];//归并完成后将结果复制回R[low..high]
} //Merge
}
上面在对logn趟循环中每趟对子序列执行两两归并其实有点混乱，可能说你在纸上画图时很简单，的确也很明了。
带式转成代码语言就比较恶心了。
可能有更好的代码格式的优化，大家可以自行设计
7.快速排序
快排是也算是冒泡的一种改进，同样的属于交换排序
基本思路是通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
整个来说是用到分治和递归的两种基本思想。
[java] view plaincopy
private static void quickSort(int[] nums, int low, int high) {
int mid;
if (low < high) {
mid = partition(nums, low, high);
quickSort(nums, low, mid - 1);
quickSort(nums, mid + 1, high);
}
}
private static int partition(int[] nums, int low, int high) {
int key = nums[low];// 设置
int temp;
while (low < high) {
while (low < high && nums[high] >= key)
high--;
if (low < high) {
temp = nums[low];
nums[low] = nums[high];
nums[high] = temp;
}
while (low < high && nums[low] <= key) {
low++;
}
if (low < high) {
temp = nums[low];
nums[low] = nums[high];
nums[high] = temp;
}
}
return low;
}
以上上快排最基本的实现。
对于快速排序的优化：第一点是中间值的选取：也就是这个key。
因为理论上来说，这个key选取的越接近中间数，那么对于分治后的左右两边越平衡，理解成树形式可以知道此刻树的深度越小，那递归层数也就越小了。
于是优化时就在对这个key取值上进行优化。现在一般就是取左端，中间，右端三个数后比较取一个处于三个数的中间的值作为最右端（因为我们函数取key值是nums[low]，即最左端的值）。此时只需将微微改动
[java] view plaincopy
private static int partition(int[] nums, int low, int high) {
int middle = low+(high-low)/2;//中间元素的下标
int temp;
if(nums[low] > nums[high]){
temp = nums[low];
nums[low] = nums[high];
nums[high] = temp;
}
if(nums[middle] > nums[high]){
temp = nums[middle];
nums[middle] = nums[high];
nums[high] = temp;
}
//以上两个if后保证最小值和中间值处于middle和low位置，下面再用一个if来保证将中间值放在low位置
if(nums[middle] > nums[low]){
temp = nums[middle];
nums[middle] = nums[low];
nums[low] = temp;
}
int key = nums[low];// 设置
while (low < high) {
while (low < high && nums[high] >= key)
high--;
if (low < high) {
temp = nums[low];
nums[low] = nums[high];
nums[high] = temp;
}
while (low < high && nums[low] <= key) {
low++;
}
if (low < high) {
temp = nums[low];
nums[low] = nums[high];
nums[high] = temp;
}
}
return low;
}
其实可以把交换那个三句的代码写个单独方法。。。我这边就随意点了。
第二点：减少交换次数。
相对来说，快排是也是属于交换排序，在一趟扫描中（即low往high靠近）时，将交换改成替换
[java] view plaincopy
private static int partition(int[] nums, int low, int high) {
int middle = low+(high-low)/2;//中间元素的下标
int temp;
if(nums[low] > nums[high]){
temp = nums[low];
nums[low] = nums[high];
nums[high] = temp;
}
if(nums[middle] > nums[high]){
temp = nums[middle];
nums[middle] = nums[high];
nums[high] = temp;
}
//以上两个if后保证最小值和中间值处于middle和low位置，下面再用一个if来保证将中间值放在low位置
if(nums[middle] > nums[low]){
temp = nums[middle];
nums[middle] = nums[low];
nums[low] = temp;
}
int key = nums[low];// 设置
while (low < high) {
while (low < high && nums[high] >= key)
high--;
if (low < high) {
nums[low] = nums[high];
// temp = nums[low];
// nums[low] = nums[high];
// nums[high] = temp;
}
while (low < high && nums[low] <= key) {
low++;
}
if (low < high) {
nums[high] = nums[low];
// temp = nums[low];
// nums[low] = nums[high];
// nums[high] = temp;
}
}
nums[low] = key;
return low;
}
这个具体怎么理解，可以画下图就觉得，的确是这么着的。
最后再提到一点改进是用尾递归，实现代码：
[java] view plaincopy
private static void quickSort2(int[] nums, int low, int high) {
int mid;
while(low < high){
mid = partition(nums, low, high);
quickSort2(nums, low, mid - 1);
low = mid +1;
}
// if (low < high) {
// mid = partition(nums, low, high);
// quickSort2(nums, low, mid - 1);
// quickSort2(nums, mid + 1, high);
// }
}
