ALGO基础（一）—— 排序

冒选插希快归堆，以下均为从小到大排

1 冒泡排序

描述：

比较相邻的元素。如果第一个比第二个大，就交换它们两个；
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
针对所有的元素重复以上的步骤，除了最后一个；
重复步骤1~3，直到排序完成。

public void bubbleSort(int[] nums){   //每次从头开始把最大的放到最后int len = nums.length;for(int i = 0;i<len-1;i++){    [0，len-1)for(int j = 0;j<len-i-1;j++){   [0，len-i-1)if(nums[j]>nums[j+1]){int tmp = nums[j];nums[j] = nums[j+1];nums[j+1] = tmp;}}}}

2 选择排序

在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。

public void select(int[] nums){int len = nums.length-1;for(int i = 0;i<len-1;i++){   [0.len-1)int index = i;  //最小值下标for(int j = i+1;j<len;j++)  [i+1,len)if(nums[j]<nums[index]) index = j;//交换int tmp = nums[i];nums[i] = nums[index];nums[index] = tmp;}}

3 插入排序

一次插一个，插一个排一次

public void insert(int[] nums){int len = nums.length;// 从下标为1的元素开始选择位置插入，因为下标为0的只有一个元素，默认是有序的for (int i = 1; i < len; i++) {   [1,len)int temp = nums[i];  // 记录要插入的数据// 从已经排序的序列最右边的开始比较，找到比其小的数for (int j = i; j > 0&&nums[j-1] > temp; j--)  [i.0)  j-- &&         			nums[j] = nums[j-1];nums[j] = temp;}}

4 希尔排序(最小增量排序)

先将要排序的一组数按某个增量step（n/2,n为要排序数的个数）分成若干组，每组中记录的下标相差d.对每组中全部元素进行插入排序，然后再用一个较小的增量（step/2）对它进行分组，在每组中再进行直接插入排序。当增量减到1时，进行直接插入排序后，排序完成
希尔排序为什么效率高？

插入排序如果在后面来了一个特别小的元素，需要全部移动，那么排序的效率特别低。
希尔排序最重要的就是步长，让步长不断地除以二，直到步长为1，优点是如果在数组最后加入一个小元素，他会被很快移到最前面。

public static void shellSort(int[] nums) {int len = nums.length;int temp;for (int step = len / 2; step >= 1; step /= 2) {// 从下标为step的元素开始选择位置插入，因为前面的魅族只有1个，默认是有序的for (int i = step; i < len; i++) {   [step,len)temp = nums[i];  // 记录要插入的数据// 从已经排序的组序列最右边的开始比较，找到比其小的数for (int j = i; j > 0&&nums[j-step] > temp; j-=step)  [i.0)  j- &&         				nums[j] = nums[j-step];nums[j] = temp;}}}

5 快速排序

选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描，将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。

public void quick(int[] nums, int low, int high) {if (low < high) {int middle = getMiddle(nums, low, high);// 将数组进行一分为二quick(nums, low, middle - 1); // 对低字表进行递归排序quick(nums, middle + 1, high);// 对高字表进行递归排序}}private int getMiddle(int[] nums, int low, int high) {int tmp = nums[low]; // 数组的第一个作为中轴while (low < high) {while (low < high && nums[high] >= tmp) {high--;}nums[low] = nums[high]; // 比中轴小的记录移到低端while (low < high && nums[low] <= tmp) {low++;}nums[high] = nums[low]; // 比中轴大的记录移到高端}nums[low] = tmp; // 中轴记录到尾return low; // 返回中轴的位置}

6 归并排序

归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。自上而下的递归。

public void mergeSort(int[] nums,int left,int right){if(left<right){//找出中间索引int center=(left+right)/2;//对左边数组进行递归mergeSort(nums,left,center);//对右边数组进行递归mergeSort(nums,center+1,right);//合并merge(nums,left,center,right);}}private void merge(int[] nums, int left, int center, int right) {int [] tmpArr=new int[nums.length];int mid=center+1;//third记录中间数组的索引int third=left;int tmp=left;while(left<=center&&mid<=right){//从两个数组中取出最小的放入中间数组if(nums[left]<=nums[mid]){tmpArr[third++]=nums[left++];}else{tmpArr[third++]=nums[mid++];}}//剩余部分依次放入中间数组while(mid<=right){tmpArr[third++]=nums[mid++];}while(left<=center){tmpArr[third++]=nums[left++];}//将中间数组中的内容复制回原数组while(tmp<=right){nums[tmp]=tmpArr[tmp++];}}