插入排序
从未排序序列的最左端开始拿取一个数据，与已排序序列从右向左进行比较，如果未排序数据大于已排序序列则插入在这个已排序的数据的后面。
public static int[] insertionSort(int[] array) { if (array.length == 0) return array; int current; for (int i = 0; i < array.length - 1; i++) { current = array[i + 1]; int preIndex = i; while (preIndex >= 0 && current < array[preIndex]) { array[preIndex + 1] = array[preIndex]; preIndex--; } array[preIndex + 1] = current; } return array; }
希尔排序
插入排序的升级版，就是按照增量gap来分组，每间隔gap的数据为一组，每组分别进行简单插入排序，gap从length/2开始，每次gap=gap/2，直到gap=1，就相当于简单插入排序了。
实质就是通过按照增量gap，分成不同的组，每组提前进行简单插入排序，可以提前缩小数据之间的波动幅度，所以当gap=1的时候，整个序列的差异已经小了很多，这就是希尔排序在简单插入排序的基础之上进行的优化，以至于时间复杂度进入O(n2)以内。
代码
public static int[] ShellSort(int[] array) { int len = array.length; int temp, gap = len / 2; while (gap > 0) { for (int i = gap; i < len; i++) { temp = array[i]; int preIndex = i - gap; while (preIndex >= 0 && array[preIndex] > temp) { array[preIndex + gap] = array[preIndex]; preIndex -= gap; } array[preIndex + gap] = temp; } gap /= 2; } return array; }
选择排序
在未排序序列中选出最小值，放在已排序序列的最后边
代码
public static int[] selectionSort(int[] array) { if (array.length == 0) return array; for (int i = 0; i < array.length; i++) { int minIndex = i; for (int j = i; j < array.length; j++) { if (array[j] < array[minIndex]) //找到最小的数 minIndex = j; //将最小数的索引保存 } int temp = array[minIndex]; array[minIndex] = array[i]; array[i] = temp; } return array; }
冒泡排序
未排序序列中相邻两两数据相比较，如果前边的大于后边的，则交换，一直移动到未排序序列结束
public static int[] bubbleSort(int[] array) { if (array.length == 0) return array; for (int i = 0; i < array.length; i++) for (int j = 0; j < array.length - 1 - i; j++) if (array[j + 1] < array[j]) { int temp = array[j + 1]; array[j + 1] = array[j]; array[j] = temp; } return array; }
归并排序
归并排序利用了分治法的思想，通过递归将整个序列分为划分为越来越小的子序列，直到每个子序列都不可再分，则对子序列进行排序，然后合并已排序的子序列。
特点：稳定，但是需要额外的空间
代码
public class MergeSort { public static void merSort(int[] arr,int left,int right){ if(left<right){ int mid = (left+right)/2; merSort(arr,left,mid);//左边归并排序，使得左子序列有序 merSort(arr,mid+1,right);//右边归并排序，使得右子序列有序 merge(arr,left,mid,right);//合并两个子序列 } } private static void merge(int[] arr, int left, int mid, int right) { int[] temp = new int[right - left + 1];//ps：也可以从开始就申请一个与原数组大小相同的数组，因为重复new数组会频繁申请内存 int i = left; int j = mid+1; int k = 0; while(i<=mid&&j<=right){ if (arr[i] < arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; } } while(i<=mid){//将左边剩余元素填充进temp中 temp[k++] = arr[i++]; } while(j<=right){//将右序列剩余元素填充进temp中 temp[k++] = arr[j++]; } //将temp中的元素全部拷贝到原数组中 for (int k2 = 0; k2 < temp.length; k2++) { arr[k2 + left] = temp[k2]; } } public static void main(String args[]){ int[] test = {9,2,6,3,5,7,10,11,12}; merSort(test,0,test.length-1); for(int i=0; i<test.length;i++){ System.out.print(test[i] + " "); } } }
快速排序
快速排序也是利用了分治法的思想，
代码
public class TestQuickSort { private static int partition(int[] arr, int low, int high) { //指定左指针i和右指针j int i = low; int j= high; //将第一个数作为基准值。挖坑 int x = arr[low]; //使用循环实现分区操作 while(i<j){//5 8 //1.从右向左移动j，找到第一个小于基准值的值 arr[j] while(arr[j]>=x && i<j){ j--; } //2.将右侧找到小于基准数的值加入到左边的（坑）位置， 左指针想中间移动一个位置i++ if(i<j){ arr[i] = arr[j]; i++; } //3.从左向右移动i，找到第一个大于等于基准值的值 arr[i] while(arr[i]<x && i<j){ i++; } //4.将左侧找到的打印等于基准值的值加入到右边的坑中，右指针向中间移动一个位置 j-- if(i<j){ arr[j] = arr[i]; j--; } } //使用基准值填坑，这就是基准值的最终位置 arr[i] = x;//arr[j] = x; //返回基准值的位置索引 return i; //return j; } private static void quickSort(int[] arr, int low, int high) {//???递归何时结束 if(low < high){ //分区操作，将一个数组分成两个分区，返回分区界限索引 int index = partition(arr,low,high); //对左分区进行快排 quickSort(arr,low,index-1); //对右分区进行快排 quickSort(arr,index+1,high); } } public static void quickSort(int[] arr) { int low = 0; int high = arr.length-1; quickSort(arr,low,high); } public static void main(String[] args) { //给出无序数组 int arr[] = {72,6,57,88,60,42,83,73,48,85}; //输出无序数组 System.out.println(Arrays.toString(arr)); //快速排序 quickSort(arr); //partition(arr,0,arr.length-1); //输出有序数组 System.out.println(Arrays.toString(arr)); } }
堆排序
通过构造最大堆或者最小堆，交换顶堆元素与未排序序列元素，然后重新构造最大堆或者最小堆，直到已排序序列为n-1
步骤
代码
//声明全局变量，用于记录数组array的长度； static int len; /** * 堆排序算法 * * @param array * @return */ public static int[] HeapSort(int[] array) { len = array.length; if (len < 1) return array; //1.构建一个最大堆 buildMaxHeap(array); //2.循环将堆首位（最大值）与末位交换，然后在重新调整最大堆 while (len > 0) { swap(array, 0, len - 1); len--; adjustHeap(array, 0); } return array; } /** * 建立最大堆 * * @param array */ public static void buildMaxHeap(int[] array) { //从最后一个非叶子节点开始向上构造最大堆 for (int i = (len/2 - 1); i >= 0; i--) { //感谢 @让我发会呆 网友的提醒，此处应该为 i = (len/2 - 1) adjustHeap(array, i); } } /** * 调整使之成为最大堆 * * @param array * @param i */ public static void adjustHeap(int[] array, int i) { int maxIndex = i; //如果有左子树，且左子树大于父节点，则将最大指针指向左子树 if (i * 2 < len && array[i * 2] > array[maxIndex]) maxIndex = i * 2; //如果有右子树，且右子树大于父节点，则将最大指针指向右子树 if (i * 2 + 1 < len && array[i * 2 + 1] > array[maxIndex]) maxIndex = i * 2 + 1; //如果父节点不是最大值，则将父节点与最大值交换，并且递归调整与父节点交换的位置。 if (maxIndex != i) { swap(array, maxIndex, i); adjustHeap(array, maxIndex); } }
原文：https://www.cnblogs.com/flyandling/p/13170575.html