八大排序算法（java语言实现编写）
冒泡排序
public static void popSort(int[] array) { for (int i = 0; i < array.length; i++) { for (int j = 0; j < array.length-i-1; j++) {//每次遍历都会使一个最大的数归位 if (array[j] > array[j + 1]) { swap(array, j, j + 1); } } } } /**
* 交换数组array中下标为j、i的元素
* @param array
* @param j
* @param i
*/ private static void swap(int[] array, int j, int i) { int tmp = array[j]; array[j] = array[i]; array[i] = tmp; }
冒泡排序核心思想就是每次将两个相邻元素对比，并且把较大的元素放在后面。如此一来每次遍历都会使一个最大的元素到达其排序完成后的位置，比如第一次遍历时就会将最大的一个元素放到最后一个位置。那么只要遍历N（数组元素数量）遍就会使得所有元素均到达其应该在的位置。在第二层循环是这样写的for (int j = 0; j < array.length-i-1; j++)之所以要使array.length-i也就是这个原因，之后的元素已经是排好序的了，所以并不需要继续遍历下去，当然即使不减去i也可以正常完成排序。因为遍历它们也不会对结果造成影响。时间复杂度就是O(n)*O(n)=O(n^2)。从上面的代码也可以看出冒泡排序是稳定的，相同元素在排序过程中并不会改变相对位置。无论是对有序还是无序的数组，遍历次数都是一样的，只是有序数组不会进行交换操作，对时间复杂度无影响。
插入排序
public static void insertSort(int[] array) { for (int i = 1; i < array.length; i++) { int tmp = array[i]; int j = i; while (j > 0 && array[j - 1] > tmp) {//将大于tmp的数往后移 array[j] = array[j - 1]; j--; } array[j] = tmp;//插入 } } 插入排序也叫直接插入排序，核心思想是假设在第i个数字之前的数组元素是有序的。那么只需要从第i个元素向前遍历将比第i个数字大的元素往后移，碰到比i小的元素就插入进去即可。
希尔排序
希尔排序就是直接插入排序的改进版，也属于一种插入排序。改进的地方在与，每次遍历设置一个步长然后进行直接插入排序，完成一次遍历就将步长减半，直到步长小于等于1。由于每次移动都会移动一个步长的距离，而直接插入排序每次移动只移动一步，所以希尔排序的效率是要比直接插入排序的效率要高的。
public static void shellSort(int[] array) { int step = array.length; while (true) { step /= 2; for (int i = 0; i < step; i++) { for (int j = i + step; j < array.length; j += step) { int tmp = array[j]; int k = j; while (k >=step && array[k - step] > tmp) {//将大于tmp的数往后移 array[k] = array[k - step]; k-=step; } array[k] = tmp;//插入 } } if (step <= 1) return; } } 快速排序
public static void fastSort(int[] array) { if (array == null) throw new NullPointerException(); fastSortHelp(array, 0, array.length - 1); } private static void fastSortHelp(int[] array, int left, int right) { if (right > left) { int index = getIndex(array, left, right); fastSortHelp(array, left, index - 1); fastSortHelp(array, index + 1, right); } } private static int getIndex(int[] array, int left, int right) { int tmp = array[left]; while (left < right) { while (left < right && array[right] > tmp) {//找到第一个比tmp小的数 right--; } if (left < right) { array[left] = array[right]; left++; } while (left < right && array[left] < tmp) { left++; } if (left < right) { array[right] = array[left]; right--; } } array[left] = tmp; return left; }
快速排序是一个常用的排序算法，当数组顺序越混乱它的效率越高。用来求数组的第k大的元素也非常好用。getIndex(int[] array, int left, int right)这一个方法是核心，它将所有大于array[left]的元素放在右边，小于它的放在左边，那么就得到了array[left]排序完成后的坐标，然后对它的左右子数组分别递归调用快速排序，即可完成排序。也正是由于这个方法的特性，每次调用getIndex()方法就会使得一个元素回到它应该在的位置。所以这个方法返回的下标k就是第k大或者第k小的元素。
归并排序
归并排序是一个非原地排序算法，他需要用额外O(n)的空间来储存排序完成后的数组，然后返回这一个排好序的数组，对原数组并不会改动。这一特性可用于一些不希望改变原数组的情况，且免于对原数组进行拷贝。核心思想就是’分而治之’，每次将数组分为左右两半，然后对这两个子数组继续递归调用，直到不能分割，然后在回溯过程中将左右数组合并。合并过程就是排序过程，申请一个足够容纳左右子数组所有元素的新数组，然后每次取出左右数组中较小/较大的元素，放入新的数组，以此保证新数组有序。然后将这个新的数组返回，完成排序。
public static int[] mergeSort(int[] array) { if (array == null) throw new NullPointerException(); array = mergeSortHelp(array, 0, array.length - 1); return array; } private static int[] mergeSortHelp(int[] array, int start, int end) { if (start == end) return new int[]{array[start]}; else { int mid = (end + start) / 2; int[] leftArray = mergeSortHelp(array, start, mid); int[] rightArray = mergeSortHelp(array, mid + 1, end); return mergeArray(leftArray, rightArray); } } private static int[] mergeArray(int[] leftArray, int[] rightArray) { int[] newArray = new int[leftArray.length + rightArray.length]; int nIndex = 0, lIndex = 0, rIndex = 0; while (lIndex < leftArray.length && rIndex < rightArray.length) {//每次取出一个较大的数复制到新数组 newArray[nIndex++] = leftArray[lIndex] > rightArray[rIndex] ? rightArray[rIndex++] : leftArray[lIndex++]; } while (lIndex < leftArray.length) { newArray[nIndex++] = leftArray[lIndex++]; } while (rIndex < rightArray.length) newArray[nIndex++] = rightArray[rIndex++]; return newArray; } 选择排序
public static void selectSort(int[] array) { //每次选择最小元素，放在第一个位置 for (int i = 0; i < array.length; i++) { int minIndex = i; for (int j = i + 1; j < array.length; j++) {//获得最小元素下标 if (array[j] < array[minIndex]) minIndex = j; } swap(array,i,minIndex); } } 也叫简单选择排序，这名字也确实符合它的特点。这个算法很简单，第i次遍历从数组后length-i个元素里找到最小的元素，然后将它放在第i个。就相当于与有两个数组，每次从没有排序的数组里移除一个最小的元素，放到排好序的数组里，直到没有排序的数组元素都被移除。
堆排序
堆排序也是一种选择排序，同样是每次遍历拿出一个最大/最小的数字放到数组尾部（这么说并不准确，应该说是放到已排序数组的头部，只不过我们在原地排序，这个已排序数组我们将其放在原始数组的尾部，所以叫它尾部）然后继续对数组进行同样的操作，直到所有数字均被取出。与简单选择排序不同的是，我们维护一个堆，每次堆顶元素都是未排序数组的最大值。这样取出最大元素的操作就不必每次遍历所有未排序元素了。
public static void heapSort(int[] array) { //把数组当成满二叉树 //i结点的左孩子下标为i*2+1. for (int i = array.length / 2 - 1; i >= 0; i--) {//构建大顶堆 siftDown(array, i, array.length); } for (int i = array.length - 1; i >= 0; i--) {//将堆顶元素放置最后（堆大小-1），然后重新构建大顶堆 swap(array, 0, i); siftDown(array, 0, i); } } private static void siftDown(int[] array, int i, int length) { int key = array[i]; int half = length >>> 1; while (i < half) { int child = (i << 1) + 1; if (child + 1 < length && array[child] < array[child + 1]) { child++; } if (array[child] <= key) { break; } array[i] = array[child]; i = child; } array[i] = key; }
siftDown(int[] array, int i, int length)是一个下沉操作，它将第i个元素下沉。那么何种情况会下沉呢？当子节点比它大时就下沉，将较大的元素上浮。这样可以保证对于堆中的任意一个节点，它的所有子孙节点都比它小。Java中的PriorityQueue就是采用的这种方式维护大顶堆/小顶堆。下面是PriorityQueue中的一段源码:
private static <T> void siftDownComparable(int k, T x, Object[] es, int n) { // assert n > 0; Comparable<? super T> key = (Comparable<? super T>)x; int half = n >>> 1; // loop while a non-leaf while (k < half) { int child = (k << 1) + 1; // assume left child is least Object c = es[child]; int right = child + 1; if (right < n && ((Comparable<? super T>) c).compareTo((T) es[right]) > 0) c = es[child = right]; if (key.compareTo((T) c) <= 0) break; es[k] = c; k = child; } es[k] = key; } 基数排序/桶排序
…那个本人也还没有掌握这种算法，手撕不出来。且容我学习一会再更…
本文地址：https://blog.csdn.net/First_C0de/article/details/107958580