基础排序算法介绍 知识点:
算法
平均时间
最好
最差
空间复杂度
稳定性
冒泡排序
$ O(n^2) $
$ O(n) $
$ O(n^2) $
$ O(1) $
稳定
直接插入排序
$ O(n^2) $
$ O(n) $
$ O(n^2) $
$ O(1) $
稳定
折半插入排序
$ O(nlogn) $
$ O(nlogn) $
$ O(n^2) $
$ O(1) $
稳定
希尔排序
$ O(nlogn) $ - $ O(n^2) $
$ O(n^1.3) $
$ O(n^2) $
$ O(1) $
不稳定
选择排序
$ O(n^2) $
$ O(n^2) $
$ O(n^2) $
$ O(1) $
不稳定
快速排序
$ O(nlogn) $
$ O(nlogn) $
$ O(n^2) $
$ O(nlogn) $ - $ O(n^2) $
不稳定
归并排序
$ O(nlogn) $
$ O(nlogn) $
$ O(nlogn) $
$ O(n) $
稳定
堆排序
$ O(nlogn) $
$ O(nlogn) $
$ O(nlogn) $
$ O(1) $
不稳定
排序算法 冒泡排序
在要排序的一组数中,对当前范围内还未排列好的数据由上而下进行比较,即每当相邻的数与要求的排序方式相反时将数据进行互换 改进版的写法就是利用标记法减少循环次数
基本写法1 2 3 4 5 6 7 8 9 10 private static void bubbleSort(int [] array) { int size = array.length; for (int i = 0; i < size - 1; i++) { for (int j = 1; j < size - i; j++) { if (array[j - 1] > array[j]) { swap(array, j, j - 1); } } } }
改进写法1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 private static void advancedBubbleSort(int [] array) { int size = array.length; int flag = 0;//设置标记位 for (int i = 0; i < size - 1; i++) { flag = 0; for (int j = 1; j < size - i; j++) { if (array[j - 1] > array[j]) { flag = 1; swap(array, j, j - 1); } } if (flag == 0)//没有发生数据交换则意味着排序已经结束 break ; } }
选择排序
再一次遍历过程中找到最小值放在排序数据中的首位,每次寻找剩余中最小的直到结束为止。
1 2 3 4 5 6 7 8 9 10 11 12 private static void selectSort(int [] array) { int size = array.length; for (int i = 0; i < size; i++) { int minIndex = i; for (int j = i + 1; j < size; j++) { if (array[j] < array[minIndex]) { minIndex = j; } } swap(array, i, minIndex); } }
直接插入排序
按照顺序选定元素从后往前找,插入一个顺序数列中即可
1 2 3 4 5 6 7 8 9 10 private static void InsertSort(int [] array) { int size = array.length; for (int i = 0; i < size; i++) { int temp = array[i]; for (int j = i; j > 0 && array[j - 1] > array[j]; j--) {//从该元素所在位置 向前移动 直到该元素位于 递增顺序 array[j] = array[j - 1]; array[j - 1] = temp; } } }
折半插入排序
再往前寻找位置的过程中利用二分法寻找位置
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 private static void insertBinarySort(int [] array) { int size = array.length; for (int i = 1; i < size; i++) { if (array[i] < array[i - 1]) {//前比后大 int temp = array[i]; int low = 0, high = i - 1, mid; while (low <= high) {//直到相交或者相反 mid = (low + high) / 2;//折中取点 if (temp < array[mid]) {//小于中点则位于中点左侧 high = mid - 1; } else { low = mid + 1; } } for (int j = i; j > low; j--) { array[j] = array[j - 1]; } array[low] = temp;//低点使用temp } } }
希尔排序
先取d
为间隔,将原始数组分为d个序列,将间隔的数组放在一个子序列利用插入排序法进行排序 然后缩小间隔d
重复上述操作,知道d
为1时,则排序完成
1 2 3 4 5 6 7 8 9 10 11 12 13 private static void shellSort(int [] array) { int size = array.length; for (int d = size / 2; d > 0; d /= 2) {//设置步长 for (int i = 0; i < size; i += d) { int temp = array[i]; int j = i; for (; j >= d && temp < array[j - d]; j -= d) { array[j] = array[j - d]; } array[j] = temp; } } }
基数排序
讲一组元素进行桶分配,按照每位数的大小进行排序
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 private static void radixSort(int [] array) { int size = array.length; int max = array[0];//数组中的最大数 for (int i = 0; i < size; i++) { if (array[i] > max) max = array[i]; } int time = 0;//最大位数 while (max > 0) { max /= 10; time++; } int k = 0;//索引 int m = 1;//位值 int n = 1;//第几位 int [][] temp = new int [10][size]; int [] order = new int [10]; while (m <= time) { for (int arr : array) { int lsd = (arr / n) % 10; temp[lsd][order[lsd]] = arr; order[lsd]++; } for (int i = 0; i < 10; i++) { if (order[i] != 0) { for (int j = 0; j < order[i]; j++) { array[k] = temp[i][j]; k++; } } order[i] = 0; } n *= 10; k = 0; m++; } }
快速排序
通过排序将待排序记录分成两部分,其中一部分记录的关键字均比另一部分小,然后分别对这两部分进行排序,直到整个序列有序。快速排序在元素很少时,效率很低
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 private static void quickSort(int [] arr,int l,int r){ if (l>=r) return; int p=getMiddle(arr,l,r);//取出中点 quickSort(arr,l,p-1);//对左侧进行排序 quickSort(arr,p+1,r);//对右侧进行排序 } private static int getMiddle(int [] arr, int l, int r) { int temp = arr[l];//定义左侧为基点 int middle = l; for (int i = middle + 1; i <= r; i++) { if (arr[i] < temp) { swap(arr, middle + 1, i); middle++; } } swap(arr, l, middle); return middle; }
归并排序
把待排序序列分成若干个有序子序列,然后再把子序列合并成一个有序序列。
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 private static void mergeSort(int [] arr, int l, int r) { int mid = (l + r) / 2; if (l < r) { mergeSort(arr, l, mid); mergeSort(arr, mid + 1, r); merge(arr, l, mid, r); } }private static void merge(int [] arr, int low, int mid, int high) { int [] temp = new int [high - low + 1]; //左指针 int i = low; //右指针 int j = mid + 1; int index = 0; //把较小的数 移动到新数组中 while (i <= mid && j <= high) { if (arr[i] < arr[j]) { temp[index++] = arr[i++]; } else { temp[index++] = arr[j++]; } } //把左边剩余的数移到新数组中 while (i <= mid) { temp[index++] = arr[i++]; } //把右边剩余的数移到新数组中 while (j <= high) { temp[index++] = arr[j++]; } //得到新的数据 覆盖原有部分 System.arraycopy(temp, 0, arr, low, temp.length); }
堆排序
将数组构成大堆二叉树,即父节点比子节点大的二叉树,然后每次将根节点放在最后一位,循环遍历
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 /** * 堆排序 * @param arr */private static void heapSort(int [] arr) { //预先构建一次大堆二叉树 buildMaxHeap(arr); int length = arr.length; for (int i = length - 1; i > 0; i--) { swap(arr, 0, i); maxHeap(arr, i, 0); } } /** * */private static void buildMaxHeap(int [] arr) { int length = arr.length; for (int i = length / 2 - 1; i >= 0; i--) { maxHeap(arr, length, i); } } /** * 构建大堆二叉树节点 */private static void maxHeap(int [] arr, int length, int node) { int left = 2 * node + 1; int right = 2 * node + 2; int maxIndex = node; if (left < length && arr[left] > arr[maxIndex]) { maxIndex = left; } if (right < length && arr[right] > arr[maxIndex]) { maxIndex = right; } //如果不是父节点最大,则找到最大的子节点进行调换 if (maxIndex != node) { swap(arr, node, maxIndex); maxHeap(arr, length, maxIndex); } }