【JavaGuide】十大经典排序算法总结

冒泡排序

算法步骤

不断的两两比较，这样当前最大的元素总是会排在最后面。所以称为冒泡。

图解算法

代码实现

public static int[] bubbleSort(int[] arr) {
	// i是排好了几个数
   for (int i = 1; i < arr.length; i++) {
	   // flag标记当前循环是否调整了顺序，如果没有调整，说明排序完成
       boolean flag = true;
       // arr.length - i控制数组尾巴
       for (int j = 0; j < arr.length - i; j++) {
           if (arr[j] > arr[j + 1]) {
               int tmp = arr[j];
               arr[j] = arr[j + 1];
               arr[j + 1] = tmp;
               flag = false;
           }
       }
       if (flag) {
           break;
       }
   }
   return arr;
}

算法分析

稳定性：稳定
时间复杂度：最佳：$O(n)$ ，最差：$O(n^2)$， 平均：$O(n^2)$
空间复杂度：$O(1)$
排序方式：内部排序

选择排序

算法步骤

不断地选择最小/最大的元素和当前未排序序列的头进行交换

图解算法

代码实现

public static int[] selectionSort(int[] arr) {
   // 找到的元素放到第i个，未排序序列头
   for (int i = 0; i < arr.length - 1; i++) {
       // minIndex记录当前未排序的最小元素的索引
       int minIndex = i;
       for (int j = i + 1; j < arr.length; j++) {
           if (arr[j] < arr[minIndex]) {
               minIndex = j;
           }
       }
       // 交换
       if (minIndex != i) {
           int tmp = arr[i];
           arr[i] = arr[minIndex];
           arr[minIndex] = tmp;
       }
   }
   return arr;
}

算法分析

稳定性：不稳定
时间复杂度：最佳：$O(n^2)$ ，最差：$O(n^2)$， 平均：$O(n^2)$
空间复杂度：$O(1)$
排序方式：内部排序

插入排序

算法步骤

就是扑克牌理牌。从前往后读取未排列序列的元素，拿到新元素后从后往前遍历已排序序列找到合适的位置插入。

图解算法

代码实现

public static int[] insertionSort(int[] arr) {
   for (int i = 1; i < arr.length; i++) {
   	  // preindex记录已排序序列的尾
       int preIndex = i - 1;
       // current是当前要插入的元素
       int current = arr[i];
       while (preIndex >= 0 && current < arr[preIndex]) {
       	  // 往后移
           arr[preIndex + 1] = arr[preIndex];
           preIndex -= 1;
       }
       arr[preIndex + 1] = current;
   }
   return arr;
}

算法分析

稳定性：稳定
时间复杂度：最佳：$O(n)$ ，最差：$O(n^2)$， 平均：$O(n^2)$
空间复杂度：$O(1)$
排序方式：内部排序

希尔排序

算法步骤

不断的按照增量来分出子数组的数量，子数组内部进行插入排序，然后缩小增量，减少分子数组的数量，然后接着插入排序，直到增量为1之后再进行一次插入排序即可。

算法图解

代码实现

public static int[] shellSort(int[] arr) {
   int n = arr.length;
   int gap = n / 2;
   while (gap > 0) {
       for (int i = gap; i < n; i++) {
           int current = arr[i];
           int preIndex = i - gap;
           // 插入排序
           while (preIndex >= 0 && arr[preIndex] > current) {
               arr[preIndex + gap] = arr[preIndex];
               preIndex -= gap;
           }
           arr[preIndex + gap] = current;
       }
       gap /= 2;
   }
   return arr;
}

算法分析

稳定性：不稳定
时间复杂度：最佳：$O(nlogn)$， 最差：$O(n^2)$ 平均：$O(nlogn)$
空间复杂度：$O(1)$
排序方式：内部排序

归并排序

算法步骤

将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
就是让子数列内部有序，然后让两个子序列段间有序，不断重复直到整个序列有序。

图解算法

代码实现

public static int[] mergeSort(int[] arr) {
   if (arr.length <= 1) {
       return arr;
   }
   int middle = arr.length / 2;
   int[] arr_1 = Arrays.copyOfRange(arr, 0, middle);
   int[] arr_2 = Arrays.copyOfRange(arr, middle, arr.length);
   return merge(mergeSort(arr_1), mergeSort(arr_2));
}

public static int[] merge(int[] arr_1, int[] arr_2) {
   int[] sorted_arr = new int[arr_1.length + arr_2.length];
   int idx = 0, idx_1 = 0, idx_2 = 0;
   while (idx_1 < arr_1.length && idx_2 < arr_2.length) {
       if (arr_1[idx_1] < arr_2[idx_2]) {
           sorted_arr[idx] = arr_1[idx_1];
           idx_1 += 1;
       } else {
           sorted_arr[idx] = arr_2[idx_2];
           idx_2 += 1;
       }
       idx += 1;
   }
   if (idx_1 < arr_1.length) {
       while (idx_1 < arr_1.length) {
           sorted_arr[idx] = arr_1[idx_1];
           idx_1 += 1;
           idx += 1;
       }
   } else {
       while (idx_2 < arr_2.length) {
           sorted_arr[idx] = arr_2[idx_2];
           idx_2 += 1;
           idx += 1;
       }
   }
   return sorted_arr;
}

算法分析

稳定性：稳定
时间复杂度：最佳：$O(nlogn)$， 最差：$O(nlogn)$， 平均：$O(nlogn)$
空间复杂度：$O(n)$
排序方式：外部排序

快速排序

算法步骤

从序列中随机挑出一个元素，做为 基准；通过一趟排序将待排序列分隔成独立的两部分，比基准小的在左边，比基准大的在右边，则可分别对这两部分子序列继续进行排序，以达到整个序列有序。

图解算法

代码实现

public static int partition(int[] array, int low, int high) {
   int pivot = array[high];
   int pointer = low;
   for (int i = low; i < high; i++) {
       if (array[i] <= pivot) {
           int temp = array[i];
           array[i] = array[pointer];
           array[pointer] = temp;
           pointer++;
       }
       System.out.println(Arrays.toString(array));
   }
   int temp = array[pointer];
   array[pointer] = array[high];
   array[high] = temp;
   return pointer;
}
public static void quickSort(int[] array, int low, int high) {
   if (low < high) {
       int position = partition(array, low, high);
       quickSort(array, low, position - 1);
       quickSort(array, position + 1, high);
   }
}

算法分析

稳定性：不稳定
时间复杂度：最佳：$O(nlogn)$， 最差：$O(n^2)$，平均：$O(nlogn)$
空间复杂度：$O(logn)$
排序方式：内部排序

堆排序

算法步骤

堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆的性质：即子结点的值总是小于（或者大于）它的父节点。

图解算法

算法分析

稳定性：不稳定
时间复杂度：最佳：$O(nlogn)$， 最差：$O(nlogn)$， 平均：$O(nlogn)$
空间复杂度：$O(1)$
排序方式：内部排序

计数排序

算法步骤