排序 排序这东西可太重要了,去年学数据结构就晓得有那么多排序了,现在好像连冒泡和选择都还没彻底搞明白。
这篇文章的主要内容:
冒泡排序
选择排序
插入排序
希尔排序
归并排序
快速排序
堆排序
还有一些排序,比如基数排序和桶排序,代码还没写过,感觉好像挺恶心的,先不管了。
冒泡排序 冒泡排序的英语名是Bubble Sort,是一种最基础的交换排序。
说白了,就是两层循环,外面一层从0到len-1,里面一层从0到 len-i-1,内层for里面进行j与j+1的比较。
这样内层for循环结束之后,最大的值就会冒泡到最右边,以此类推……
1 2 3 4 5 6 7 8 9 10 11 public static void sort (int [] arr) { for (int i = 0 ; i < arr.length-1 ; i++) { for (int j = 0 ; j < arr.length-1 -i; j++) { if (arr[j]>arr[j+1 ]){ int temp = arr[j]; arr[j] = arr[j+1 ]; arr[j+1 ] = temp; } } } }
冒泡优化 :冒泡有一个最大的问题就是这种算法不管不管你有序还是没序,闭着眼睛把你循环比较了再说。有时候本来就是一个有序的或者冒泡几次就已经有序了,没必要在进行循环了。针对这个问题,我们可以设定一个临时遍历来标记该数组是否已经有序,如果有序了就不用遍历了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 public static void sortImprove (int [] arr) { for (int i = 0 ; i < arr.length-1 ; i++) { boolean isSorted = true ; for (int j = 0 ; j < arr.length-1 -i; j++) { if (arr[j]>arr[j+1 ]){ int temp = arr[j]; arr[j] = arr[j+1 ]; arr[j+1 ] = temp; isSorted = false ; } } if (isSorted) break ; } }
选择排序 首先,找到数组中最小的元素,拎出来,将它和数组的第一个元素交换位置,第二步,在剩下的元素中继续寻找最小的元素,拎出来,和数组的第二个元素交换位置,如此循环,直到整个数组排序完成。
1 2 3 4 5 6 7 8 9 10 11 12 public static void sort (int [] arr) { for (int i = 0 ; i < arr.length; i++) { int min = i; for (int j = i+1 ; j < arr.length; j++) { if (arr[j]<arr[min]) min = j; } int temp = arr[min]; arr[min] = arr[i]; arr[i] = temp; } }
插入排序 插入排序的思想和我们打扑克摸牌的时候一样,从牌堆里一张一张摸起来的牌都是乱序的,我们会把摸起来的牌插入到左手中合适的位置,让左手中的牌时刻保持一个有序的状态。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 public static void sort (int [] arr) { for (int i = 1 ; i < arr.length; i++) { int temp = arr[i]; int j; for (j = i-1 ; j >= 0 ; j--) { if (arr[j]>temp){ arr[j+1 ] = arr[j]; }else { break ; } } arr[j+1 ] = temp; } }
希尔排序 插入排序在小规模数据或者基本有序时十分高效,怎么对插入排序进行改进,是的它对较大规模并且无序的数据也非常有效率,希尔排序就可以实现它。
首先它把较大的数据集合分割成若干个小组(逻辑上分组),然后对每一个小组分别进行插入排序,此时,插入排序所作用的数据量比较小(每一个小组),插入的效率比较高。
每个分组进行插入排序后,各个分组就变成了有序的了(整体不一定有序)
然后缩小增量为上个增量的一半;继续划分分组,此时,每个分组元素个数多了,但是,数组变的部分有序了,插入排序效率同样比高
同理对每个分组进行排序(插入排序),使其每个分组各自有序
依次类推,则整个数组被分为一组,此时,整个数组已经接近有序了,插入排序效率高,对这仅有的一组数据进行排序,排序完成
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 public static void sort (int [] arr) { int len = arr.length; int gap = len/2 ; while (gap>0 ){ for (int i = gap; i < len; i++) { int temp = arr[i]; int j = i-gap; while (j>=0 && temp<arr[j]){ arr[j+gap] = arr[j]; j-=gap; } arr[j+gap] = temp; } gap/=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 public class MergeSort { public static void main (String[] args) { int [] arr = new int []{5 ,1 ,6 ,3 ,7 ,2 ,4 ,8 }; int [] tempArr = new int [arr.length]; sort(arr,tempArr,0 ,arr.length-1 ); System.out.println(Arrays.toString(arr)); } public static void sort (int [] arr,int [] tempArr,int start,int end) { if (start>=end) return ; int middle = start + (end-start)/2 ; sort(arr,tempArr,start,middle); sort(arr,tempArr,middle+1 ,end); merge(arr,tempArr,start,middle,end); } public static void merge (int [] arr,int [] tempArr,int start,int middle,int end) { for (int i = start; i <= end; i++) tempArr[i] = arr[i]; int k = start; int left = start; int right = middle+1 ; while (left<=middle && right<=end){ arr[k++] = tempArr[left]<tempArr[right] ? tempArr[left++] : tempArr[right++]; } while (left<=middle) arr[k++] = tempArr[left++]; while (right<=end) arr[k++] = tempArr[right++]; } }
快速排序 快速排序的核心思想也是分治法,分而治之。它的实现方式是每次从序列中选出一个基准值,其他数依次和基准值做比较,比基准值大的放右边,比基准值小的放左边,然后再对左边和右边的两组数分别选出一个基准值,进行同样的比较移动,重复步骤,直到最后都变成单个元素,整个数组就成了有序的序列。
是冒泡排序的升级,和冒泡排序一样,都属于交换排序的一种。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 public class No6QuickSort { public static void main (String[] args) { int [] arr = new int []{5 ,6 ,1 ,2 ,8 ,7 ,4 ,3 }; quickSort(arr,0 ,arr.length-1 ); System.out.println(Arrays.toString(arr)); } public static void quickSort (int [] arr,int left,int right) { if (left >= right) return ; int pivotIndex = partition(arr,left,right); quickSort(arr,left,pivotIndex-1 ); quickSort(arr,pivotIndex+1 ,right); } }
partition
交换方法有两种,一种是单边循环法,一种是双边循环法。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 public static int partition (int [] arr, int left, int right) { int pivot = arr[left]; int mark = left; for (int i = left+1 ; i <= right; i++) { if (arr[i]<pivot){ mark++; int temp = arr[mark]; arr[mark] = arr[i]; arr[i] = temp; } } arr[left] = arr[mark]; arr[mark] = pivot; return mark; }
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 public static int partitionV2 (int [] arr, int start, int end) { int pivot = arr[start]; int left = start; int right = end; while (left!=right){ while (left<right && arr[right]>pivot) right--; while (left<right && arr[left]<=pivot) left++; if (left<right){ int temp = arr[left]; arr[left] = arr[right]; arr[right] = temp; } } arr[start] = arr[left]; arr[left] = pivot; return left; }
堆排序 堆排序顾名思义,是利用堆这种数据结构来进行排序的算法。
堆的特性:
必须是完全二叉树
任一结点的值是其子树所有结点的最大值或最小值
构建二叉堆的过程其实就是让所有非叶子节点依次下沉
二叉堆插入节点就是最后一个位置不断上浮
二叉堆删除头结点就是用最后一个元素代替头结点然后下沉
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 public class No7HeapSort { public static void main (String[] args) { int [] arr = new int []{8 ,4 ,1 ,6 ,3 ,7 ,5 ,2 }; sort(arr); System.out.println(Arrays.toString(arr)); } public static void sort (int [] arr) { int len = arr.length; buildHeap(arr,len); for (int i = len-1 ; i >0 ; i--) { int temp = arr[0 ]; arr[0 ] = arr[i]; arr[i] = temp; sink(arr,0 ,i); } } public static void buildHeap (int [] arr, int len) { for (int i = len/2 ; i >= 0 ; i--) { sink(arr,i,len); } } public static void sink (int [] arr, int i, int len) { int parent = i; int temp = arr[i]; int child = 2 *i+1 ; while (child<len){ if (child+1 <len && arr[child+1 ]>arr[child]) child++; if (temp>arr[child]) break ; arr[parent] = arr[child]; parent = child; child = 2 *child+1 ; } arr[parent] = temp; } }