数据结构与算法之排序算法
排序的稳定性 是指对于相等的元素，排序之后，任然保存2个元素的位置没有变，就是稳定的排序，反之就是不稳定排序。
- 交换排序算法
- 桶排序
交换排序算法
- 冒泡排序 ：没轮确定一个最大的数排后面
- 选择排序 ：每轮选择最小的数排前面
- 快排 : 选最后一个作为pivot（基数）, 将数据分为 左边小于 pivot， 右边大于 pivot； 分治递归， 二叉树的前序遍历思路
- 归并排序 ： 将无序的数组，分成2个子数组分别排序，然后再merge ； 分治递归， 二叉树的后续遍历思路
线性排序算法
- 桶排序
小结
常见的排序算法都是比较排序，比较排序的时间复杂度通常为 O(n^2) 或 O(nlogn)，但是如果带排序的数字有一些特俗性时，我们可以根据这来设计更加优化的排序算法。
更多技术文章、面试资料、工具教程，还请移步：http://www.javatiku.cn/
交换排序算法
排序算法的复杂度由 比较的次数 和 交换的次数 一起决定。
直接选择排序
- 从未排序的序列中选择最小的元素，与放在第一个位置的元素交换
- 依次类推，直到全部排序
在a【i,n】中最小的元素和 a[i]交换位置。空间复杂度O(1)，时间复杂度 O(n^2)
冒泡排序
- 相邻的2各元素比较，大的向后移，经过一轮比较，做大的元素排在最后
- 第二轮，第二大的元素排倒数第二个位置
- 直到全部排好
这样，即使是排好序的拿冒泡排序排序，比较的时间复杂度O(n^2)
快速排序
时间复杂度 平均复杂度 O(n * logn) ， 最坏 O(n^2)
快速排序是对冒泡排序的改进，划分交换排序。
递归一次，pivot 左边都比它小，右边都比它大。这是递归，分治的思想。
快速排序就是个二叉树的前序遍历思路，归并排序就是个二叉树的后序遍历思路
代码框架如下
void quicksort(int *a, int left, int right){
if (left<right){//加上这个，不然有死循环，造成堆栈溢出，这也是递归结束条件
int i = partion(a,left,right);//使得局部有序，i作为分隔
quicksort(a,left,i-1);
quicksort(a,i+1,right);
}
}更多技术文章、面试资料、工具教程，还请移步：http://www.javatiku.cn/
对 A[p...r] :
- 选择最后一个元素作为 pivot (基准)
- 分解：A[p..q-1] A[q+1..r],使得 A[p...q-1]< A[q] <A[q+1..r]
- 解决：递归调用 快排，对子数组A[p..q-1],A[q+1..r]排序
- 合并（子问题相互独立的，因此用分治算法就可以了）
具体步骤：
- 从数列中选择一个元素，作为基准 pivot。通常取分区的最后一个
- 重排数列，比 pivot 小得排左边，比pivot大的排右边，相等的随便。 一句话就是挖坑填数
- 递归的，使用相同的方式，重排左右两边的子序列
扫描过程分2种：
挖坑排序，2头向中间扫描，先从后向前找，再从前向后找。
单向扫描
void quicksort(int *a, int left, int right){ if (left<right)//加上这个，不然有死循环，造成堆栈溢出，这也是递归结束条件 { int i = partion(a,left,right);//使得局部有序，i作为分隔 quicksort(a,left,i-1); quicksort(a,i+1,right); } } // 挖坑填数，2边向中间扫描 int partion(int *a, int start,int end){ int i=start,j=end; int tmp = a[i]; // 这里要做越界检查 while(i<j){ // 从后向前扫描，找到第一个小于tmp的值，来填a[i] while(i<j && a[j]>=tmp){ j--; } if (i<j)//找到了,这时候a[j]为坑 { a[i++] = a[j]; } // 从左向右扫描，找一个大于 tmp的 数， 去填坑a[j] while(i<j && a[i]<tmp){ i++; } if (i<j) { a[j++]=a[i]; } } //扫描完成后，i==j a[i]=tmp; return i; }// pivot 选择 尾部节点， 代码写起来更加简单； 移动元素更方便 // 左右指针技巧 static int partition(int[] nums, int left, int right){ int pivot = nums[right];//选尾部节点作为 pivot int end = right; right--; while (left < right) { if (nums[left] <= pivot) { left ++ ; //左边指针 窗口变小 continue; } //元素比 pivot 大，右边指针 窗口变小 //swap left & right swap(nums, left, right); right--; } // 跟 pivot 元素置换 int i = 0; if (nums[left] <= pivot) { //swap left+1 & pivot i = left +1; } else {//swap left & pivot i = left ; } swap(nums, i, end); return i; }
更多技术文章、面试资料、工具教程，还请移步：http://www.javatiku.cn/
归并排序merge
分治算法(divide-and-conquer)，必然用到递归 ;
2个有序数组的合并操作是O(n)的复杂度 因此我们可以将无序的数组，分成2个子数组分别排序，然后再merge,依次类推
归并排序的步骤:
- 分解。将一个数组分成n/2个子数组,每个序列2个元素，(2路归并)
- 解决。 将各个子数组都排好序，然后 merge 2个有序数组
- 合并
归并排序的代码框架，套用二叉树的后续遍历思路，如下：
void sort(int[] nums, int low, int high) {
int mid = (low + high) / 2;
sort(nums, low, mid);
sort(nums, mid + 1, high);
/****** 后序遍历位置 ******/
// 合并两个排好序的子数组
merge(nums, low, mid, high);
/************************/
}
//合并连个有序数组； 从后往前merge
public void merge(int[] arr,int low,int mid,int high,int[] tmp){
int i = 0;
int j = low,k = mid+1; //左边序列和右边序列起始索引
while(j <= mid && k <= high){
if(arr[j] < arr[k]){
tmp[i++] = arr[j++];
}else{
tmp[i++] = arr[k++];
}
}
//若左边序列还有剩余，则将其全部拷贝进tmp[]中
while(j <= mid){
tmp[i++] = arr[j++];
}
while(k <= high){
tmp[i++] = arr[k++];
}
for(int t=0;t<i;t++){
arr[low+t] = tmp[t];
}
}
插入排序
- 第一个元素算作已经排好
- 取下一个元素，从已经排好的序列元素中，从后向前扫描
- 如果排好序的元素大于 新元素，排好序的元素移到下一个位置
- 重复3，直到直到最后的插入位置
- 重复2
类似插入扑克牌的效果
最坏的情况： 待排序的是一个逆序排放的数组，这样导致每一轮都要移动元素；此时复杂度是是0(n^2) 最好的情况： 待排序的是一已经顺序排放的数字，此时只需要做一轮比较就够了 0（n）。因此可以看到，对大部分数据已经有序这样的数组排序，使用插入排序非常有优势
空间复杂度O（1）
更多技术文章、面试资料、工具教程，还请移步：http://www.javatiku.cn/
希尔排序
递减增量排序算法，对插入排序的改进，实质是分组插入排序，又叫缩小增量排序
- 先将待排数列分割成若干子序列（增量为m)
- 对每个子序列使用插入排序
- 减小增量，再排序
- 对全体元素做一次插入排序
希尔排序提升排序的奥秘就在于数据元素越有序，使用插入排序效率越高
堆排序
利用堆这种数据结构设计的一种排序算法
我们来看看如何使用堆 来做排序?
- 将待排序数列看做一颗完全二叉树的存储结构
- 堆化数组，结束后，根a[0]变成了最小的值（小根堆）
- 取a[0]值，然后对堆做删除操作，此时，堆会重新 堆化数组，a[0]又是下一个最小的值。删除操作通常是先把数组最后的元素提到a[0]位置，然后从根节点开始进行一次从上向下的调整；调整时，先从左右孩子中找最小的交换。如果父节点比每个节点都小就不用调整。因此，在堆排序是可以直接让 a[0]和数组最后一个元素互换，但要先保存好a[0],或者a[n-1],这样导致了使用堆排序时，递增排序使用大根堆，递减排序使用小根堆。
- 循环3，就可以按从小到大的顺序取出所有数组元素。
堆排序主要时间花在建堆期间和堆化数组，找数列中最大数只需要O(1)时间复杂度
void heap_sort(int *a, int length){
// 建立堆 大根堆，递增排序
heap_build(a,length);
for (int i = length-1; i >0; --i)
{
//交换
heap_swop(&a[0],&a[i]);
//调整
heap_adjust(a,i);
}
}推排序还可以用来求 top-K 大(小)的问题。
更多技术文章、面试资料、工具教程，还请移步：http://www.javatiku.cn/
