本篇blog的语言为java实现，介意请划走
八大排序算法
冒泡排序
选择排序
插入排序
希尔排序
快速排序
归并排序
桶排序
堆排序
上述排序值得注意的是堆排序，他利用顺序二叉树实现了对堆元素的随机存取，而他所操作的虽然是数组结构，但本质上我们将其视为一个二叉树。
基本排序算法（并不复杂，甚至称不上算法，理解即可） 冒泡 1 2 3 4 5 6 7 8 9 10 11 12 public static void bubble_sort (int [] arr) { int i, j, temp, len = arr.length; for (i = 0 ; i < len - 1 ; i++) for (j = 0 ; j < len - 1 - i; j++) if (arr[j] > arr[j + 1 ]) { temp = arr[j]; arr[j] = arr[j + 1 ]; arr[j + 1 ] = temp; } }
时间复杂度（n^2）
每次排序将最大值放入末尾，且注意，该算法的核心在于逐步排序，内层循环将较小或者较大的值下沉。
选择排序 在冒泡排序中，我们逐步将最大或最小值后移，而选择排序优化了这个过程，比较过程并不移动数组元素，而是先找到将要移动的坐标。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 public static void selectionSort (int [] array) { if (array == null || array.length <= 1 ) { return ; } int length = array.length; for (int i = 0 ; i < length - 1 ; i++) { int minIndex = i; for (int j = i + 1 ; j < length; j++) { if (array[j] < array[minIndex]) { minIndex = j; } } if (i != minIndex) { swap(array, minIndex, i); } } } private static void swap (int [] array, int a, int b) { int temp = array[a]; array[a] = array[b]; array[b] = temp; }
插入排序 该思想和动态规划有点像，即我们假定要将插入某个元素插入一个有序数组，那么我们只需要从数组起点或者某位逐步比较即可。
注意：数组元素的比较必须满足a>=b,b>=c,一定能推出a>=c。
1 2 3 4 5 6 7 8 9 10 11 12 13 void insertionSort (int [] nums) { for (int i = 1 ; i < nums.length; i++) { int base = nums[i], j = i - 1 ; while (j >= 0 && nums[j] > base) { nums[j + 1 ] = nums[j]; j--; } nums[j + 1 ] = base; } }
较为复杂的排序 希尔排序 核心思想：通过步长指定分组，将每次分组内的数据变得有序。这样当我们减少步长时，虽然数组元素并不会因此有序，但是会变得相对容易排序。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 public static void shellsort (int [] arr) { int h=arr.length; while (true ){ h=h/2 ; if (h==0 ){ break ; } for (int i=h;i< arr.length;i++){ int j=i; int m=arr[j]; while (j-h>=0 &&arr[j-h]>m){ arr[j]=arr[j-h]; j-=h; } arr[j]=m; } }
快速排序 核心思想：使用基准将数据进行分组，当极限状态只剩下两个数字时，也就是完成了排序。
他和希尔排序不同的地方在于，他的分组的依据是基准，并不保证分组范围。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 /** * @author:wenzhuo4657 des: 错位交换处理基准数据，最终使其变成两个区间的边界 */ public static void example(int[] arr, int left, int right) { if (left >= right) {//越界处理 return; } int l = left; int r = right; int mid = arr[l];//1，作为基准， // 2,错位处理，解决了基准数据移动，即便是极端情况下，也会由于while循环条件只会到达l==r,而这个位置的交换是无效的，最后再将错位的arr[l]填充 // 使基准数据也参与到排序中变动位置。 while (l < r) { while (l < r && arr[r] >= mid) { r--; } arr[l] = arr[r]; while (l < r && arr[l] < mid) { l++; } arr[r] = arr[l]; } arr[l] = mid; example(arr, left, l-1); example(arr, l+1, right); }
归并排序 核心思想：递归找到两个数字的分组进行排序（其实按照递归是找到一个数字的分组，只是它的排序无效）
逐层向上将两个有序分组合并。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 public static void example(int []arr,int left,int right,int[] temp){ // 该函数主要用于实现递归调用的流程 if(left<right){ int min=(left+right)/2; example(arr,left,min,temp); example(arr,min+1,right,temp); merge(arr,left,min,right,temp);//基于归并排序的递归流程，该方法所得到的数组均是局部有序，极限情况，为两个元素的区间，例如 [0,1] } } /** * @author:wenzhuo4657 des: 该排序生效的数组必须是局部有序的数组，或者说，[left,min]升序，[min+1,right]升序 */ private static void merge(int[] arr, int left, int min, int right, int[] temp) { int i=left; int j=min+1; int t=0; // 1,两个有序区间[left,min] [min+1,right] while (i<=min&&j<=right){ if (arr[i]<=arr[j]){ temp[t]=arr[i]; i++; }else { temp[t]=arr[j]; j++; } t++; } // 2, 基于上述while循环特点，最终只剩下一边数据没有填充，并且由于区间局部有序可知，此时省下的数据可以直接顺序填充 while (i<=min){ temp[t]=arr[i]; i++; t++; } while (j<=right){ temp[t]=arr[j]; j++; t++; } // 3,填充完毕，将结果复制到原本数组的区间 t=0; for(int h=left;h<=right;h++){ arr[h]=temp[t]; t++; } }
桶排序 按照数字位数进行一次排序。
待补充
堆排序 利用顺序二叉树将树结构扁平化处理，实现随机存取，并且使用大顶堆或小顶堆结构获取某个范围内的最大值或者最小值。
值得注意的是该算法对于如何将一个树调整为堆结构的方式：假设某个树除了根节点，其余节点均符合这个条件，如何为这个根节点找到合适位置进行交换？这样做了之后他也一定能够变成大顶堆或者小顶堆结构。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 /** * @author:wenzhuo4657 des: 要将root下沉到合适的地方，且需要注意，以root为跟节点的这个子树（可能是0，就是这棵树本身），除了根节点以外，都符合大顶堆定义。 arr:顺序二叉树， root: 某个节点，这里将其视为数组在该子树中找到合适位置的节点 length;排序范围 */ public static void heap1(int arr[] ,int root,int length){ int temp=arr[root];//临时存储根节点 for (int k=root*2+1;k<length;k=k*2+1){ if (k+1<length&&arr[k]<arr[k+1]){//1,找到左右较大的那个 k++; } if (temp<arr[k]){//判断三元组 节点root和节点root的左右节点的最大值 arr[root]=arr[k];//这一步相当于是移位交换，交换目标为，root和k root=k;//不断更新root节点， }else { break; } } arr[root]=temp;//完成下沉 } public static void heap2(int []arr){ int temp=0; //转换顺序二叉树为大顶堆，arr.length/2-1==（(arr.length-1)末尾节点-1）/2 ，从最底层开始逐渐完成大顶堆定义，换言之，他的每一个子树都符合大顶堆。 for (int i=arr.length/2-1;i>=0;i--){ heap1(arr,i, arr.length); } System.out.println(Arrays.toString(arr)); //堆排序 for (int j= arr.length-1;j>0;j--){ temp=arr[j]; arr[j]=arr[0]; arr[0]=temp; heap1(arr,0, j); } }
如图的关键方法为heap1,再传入一个未知结构的树时，他通过从最后一个非叶子节点开始逐层将子树变为堆结构（通过heap1方法），最终使整个树称为堆结构。
