之前有一篇文章讲过快排。其核心思想就是：用3个指针，两个代表head & tail ，一个代表 key，在一趟排序中，将所有比 key 大的放在一边，小的放在另外一边，形成一个相对有序的数列，之后用递归，将前后两个序列继续快排，直到结束。
今天我们看一下其他的5种排序算法：选择排序、插入排序、归并排序、希尔排序、堆排序。
争取一个星期写一个，消化一个。
1. 选择排序
基础思想
这个思想非常简单。
就是每遍历一次，选择出最小的一个元素，与最前面一个位置元素做交换。
然后进行下一次遍历，从第二个位置开始。
直到遍历完。
复杂度分析
第一轮比较 (n-1) 次，第2轮 (n-2) 次。。。总共的 所以时间复杂度是
。
代码
package day_53;
// 选择排序。核心思想为每一轮遍历进行选出一个元素。然后遍历剩下的
public class SelectionSort {
public void selectionSrot(int nums[]){
for(int i=0;i<nums.length-1;i++){ //这里就是说做 n-1次选择
int index_tmp = i;
int tmp1 = nums[i];
for(int j=i;j<nums.length;j++){
// 在一轮遍历中要找出最小的元素
if(nums[j]<tmp1){
tmp1 = nums[j];
index_tmp = j;
}
}
// 完成一轮遍历之后做交换
int tmp2 = nums[index_tmp];
nums[index_tmp] = nums[i];
nums[i] = tmp2;
}
}
public static void main(String args[]){
int heights[] = {181,169,187,172,163};
SelectionSort s = new SelectionSort();
s.selectionSrot(heights);
for(int height : heights ){
System.out.print(height);
}
}
}
2. 插入排序
基础思想
基础思想很简单：即将元素插入到有序数组中即可。
插入规则：将 candidate element 依次和有序的数组进行比较，确定插入位置。有序数组最开始是第一个ele。
复杂度分析
这里的复杂度分析稍微麻烦一点。
这里有两步操作，比较和赋值。看一下别人的推导。
复杂度分析
所以，结论是：O(n^2)
代码
package day_54;
// 插入排序。
// 思想也很简单，每次将一个元素插入到有序数组中。有序数组从1个元素开始
// 插入规则是，依次比较，找到比他大的，插到前面，否则放在最后。
public class InsertionSort {
public void insertionSort(int[] nums){
for (int i=1;i<nums.length;i++){
for (int j=0;j<i;j++){
if(nums[i]<nums[j]){
// 插入操作
int tmp = nums[i];
int k = i;
while (k>j)
nums[k] = nums[--k];
nums[j] = tmp;
// 插入完成后跳出循环
break;
}
}
}
}
public static void main(String args[]){
int a[] = {99,91,3,4,2,8,6,5};
InsertionSort i = new InsertionSort();
i.insertionSort(a);
for(int ele : a){
System.out.println(ele);
}
}
}
上面是我自己写的版本。之后在写希尔排序的时候，使用了改进版的插入排序。
改进在于，从后向前，每次将元素向后移动，腾出来位置，将待插入元素插入。
public static void insertionSort2(int[] nums){
for(int i=1;i<nums.length;i++){
int j;
// 要插入的元素
int tmp = nums[i];
// 这个逻辑就是从后向前的，腾出来要插入的位置
for(j=i;j>0 && nums[j-1]>tmp;j--){
nums[j] = nums[j-1];
}
nums[j] = tmp;
}
}
3. 归并排序
思想
MergeSort的核心思想是分治。但是实际上比的思想并不是很简单，没有上面的两个直观。所以今天看了别人的步骤图，也没有直接写出来代码。还是看了别人代码的结构才慢慢写出来的。可以参考这个老哥的笔记。
这里我自己总结一下，所谓的归并就是说把 有序的数组再归并到一个数组。这里当然要用一个 tmp[] 数组增加一点空间开销来换取时间开销。
问题的关键是，这里肯定是递归的。但是怎样递归呢？首先是要 divide，然后要 merge，所做操作都是针对同一个数组的，我们只需要指定出操作数组的范围即可。
先来看 merge() 方法，这里用一个例子，想要将两个有序数组（连续的，不是两个独立的）合并成一个，需要 (left,mid,right) 三个参数，其中 mid 标记的是两者的分界。
然后看 divide() 方法，divide 方法内才是递归发生的地方。其中递归终止条件是 left==right，只有一个元素了就不再 divide 了。同时调用下一层 divide，最终到 divide结束之后，调用 merge。
层层向下，尽头merge，最终向上！
复杂度分析
divide & conqure 时间复杂度就是 ，空间复杂度是
代码
package day_55;
// 归并排序
// 核心思想是分治
// 先divide 到头才可以 merge，所以是divide中递归
public class MergeSort {
public static void mergeSort(int nums[]){
divide(nums,0,nums.length-1);
}
public static void divide(int nums[], int left, int right){
if(left==right)
return;
int mid = (left + right)/2;
divide(nums,left,mid);
divide(nums,mid+1,right);
merge(nums,left,mid,right);
}
public static void merge(int nums[],int left,int mid, int right){
// 用于暂存的数组
int tmp[] = new int[right-left+1];
int index = 0;
int r = mid+1;
int l = left;
while(l<=mid && r<=right) {
if (nums[l] <= nums[r])
{
tmp[index++] = nums[l++];
continue;
}
if (nums[r] < nums[l])
{
tmp[index++] = nums[r++];
continue;
}
}
//
if(l>mid){
for(int k=r;k<=right;k++){
tmp[index++] = nums[k];
}
}
if(r>right){
for(int k=l;k<=mid;k++){
tmp[index++] = nums[k];
}
}
// 暂存数组写回去
for(int j=0;j<tmp.length;j++){
nums[left++] = tmp[j];
}
}
public static void main(String args[]){
MergeSort m = new MergeSort();
int a[] = {21,31,32,2,3,4,98,45,10};
m.mergeSort(a);
for(int ele : a){
System.out.println(ele);
}
}
}
4. 希尔排序
思想
希尔排序可以说是插入排序的升级版。由于插入排序在小数据量和基本有序数据的基础上效率更高。所以出现了希尔排序。
希尔排序的核心思想是将待排序数组进行逻辑分组，每个分组内部使用插入排序。
通过一个 gap来控制分组，gap折半直到为1，此时排序完成。
复杂度
这里是增量时间复杂度（所谓增量就是每一次通过折半来产生新的增量）。
只需要记住结论：
代码
跟上面思路里面说的一样，其实分成两步，用 gap 控制分组，然后每个分组内用插入排序。
package day_57;
// 希尔排序是插入排序的高级版本。因为插入排序对于小规模数据或基本有序数据十分高效。
// 在此基础上，有了希尔排序。
public class ShellSort {
private void shellSort(int[] nums){
int n = nums.length;
for(int gap=n/2;gap>0;gap/=2){
for(int i=0;i<gap;i++){
// 对这一个逻辑分组进行插入排序
insertSort(nums,gap,i);
}
}
}
private void insertSort(int nums[],int gap, int i){
int k;
for(int j=i+gap;j<nums.length;j+=gap){
int tmp = nums[j];
for(k=j-gap;k>=0 && tmp<nums[k];k-=gap){
nums[k+gap] = nums[k];
}
nums[k+gap] = tmp;
}
}
public static void main(String args[]){
ShellSort s = new ShellSort();
int a[] = {2,3,5,32,13,1,44,22};
s.shellSort(a);
for (int ele : a){
System.out.println(ele);
}
}
}
5. 堆排序
思想：
堆排序的思想很简单，就是利用大根堆的特性，将数组和大根堆结合起来，通过不断建立、更新大根堆的过程来完成排序。
具体的过程参考别人的动画：https://www.jianshu.com/p/0d383d294a80
总结下来，就两步：
-
建立大根堆：这一部分是最耗时的一步，由于为了要保证“父>子”的特性，所以需要从后向前，一步步建立。
-
维护大根堆：完成大根堆建立之后，最大的元素就会被放在根节点上（即nums[0]），这时交换 nums[0] 和 nums[len-1]。交换之后大根堆并不稳定，需要重新维护大根堆，但是由于这时，大根堆基本有序，所以并不需要再从后向前维护了，只需要从前向后维护即可，即选定 root = 0. 长度递减。
复杂度分析：
代码
package day_60;
// 这是代码比较简洁的 堆排序
// 前面那个有点复杂，不过想法是Ok的
public class HeapSort2 {
package Sortings;
/**
* 堆排序。这里用了大根堆的思想。
* 堆就是一个数组实现的二叉树
* 总结下来就2步，建立大根堆和维护大根堆
* 1. 建立大根堆：要保证 父亲>儿子，所以我们从后向前建立
* 2. 维护大根堆，建堆完成后，最大的元素就在 root 上了。
*/
public class HeapSort {
public static void heapSort(int[] arr){
// 建堆，从第一个非叶子节点，从下至上，从右到左，调整结构
for(int i=(arr.length-2)/2;i>=0;i--){
shiftDown(arr,arr.length,i);
}
// 交换，去除，控制arr长度
for(int j=arr.length-1;j>0;j--){
int tmp = arr[0];
arr[0] = arr[j];
arr[j] = tmp;
shiftDown(arr,j,0);
}
}
/**
* 将当前根节点及其子树调整为大根堆
* @param arr
* @param count
* @param currentRoot
*/
public static void shiftDown(int[] arr,int count,int currentRoot){
// 如果有子节点
while(2*currentRoot+1<count){
int max = 2*currentRoot+1;
// 有右子树且右子树大
if(arr[max]<arr[max+1] && max+1<count)
max += 1;
// 只有向下换的才要继续比较，
// 如果不向下换，就不用比较了，这个节点就建堆完成了
if(arr[currentRoot]>arr[max])
break;
// 交换 max 和 cur
int tmp = arr[max];
arr[max] = arr[currentRoot];
arr[currentRoot] = tmp;
// 向下递归
currentRoot = max;
}
}
public static void main(String args[]){
int a[] = {5,2,7,3,6,1,4};
HeapSort h2 = new HeapSort();
h2.heapSort(a);
for(int ele:a){
System.out.println(ele);
}
}
}
}
网友评论