八大排序算法（java版）
共 5913字，需浏览 12分钟
· 2020-08-19
点击上方蓝色字体，选择“标星公众号”
优质文章，第一时间送达
冒泡排序
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 void siftDownComparable(int k, T x, Object[] es, int n) {
// assert n > 0;
Comparablesuper T> key = (Comparablesuper 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 &&
((Comparablesuper 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;
} 基数排序/桶排序
…那个本人也还没有掌握这种算法，手撕不出来。且容我学习一会再更…
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：
https://blog.csdn.net/First_C0de/article/details/107958580
粉丝福利：108本java从入门到大神精选电子书领取
???
?长按上方锋哥微信二维码 2 秒 备注「1234」即可获取资料以及 可以进入java1234官方微信群
感谢点赞支持下哈 