由于需要分析算法的最好时间复杂度和最坏时间复杂度, 因此这篇文章中写的排序都是从小到大的升序排序
带排序的数组为 arr,arr 的长度为 N 时间复杂度使用 TC 表示, 额外空间复杂度使用 SC 表示
好多代码都用到了交换 arr[i]和 arr[j]的地方, 这里先给出代码
- private static void swap(int[] arr, int i, int j) {
- int tmp = arr[i];
- arr[i] = arr[j];
- arr[j] = tmp;
- }
(1)插入排序
1.1 直接插入排序
算法思想:
初始时第一个元素是有序的, 在插入元素 arr[i]时, arr[0] ~arr[i - 1]已经是有序的了, 将 arr[i]插入其中即可
稳定性:
如果遇到和 arr[i]相等的元素, 那么将 arr[i]放在后面, 所以直接插入排序是稳定的
复杂度分析:
arr 基本有序 (升序) 时, 直接插入排序的 TC 是 O(N);arr 降序时, TC 是 O(N*N); 平均时间复杂度 O(N*N)直接插入排序的 SC 是 O(1)
算法实现:
- public class InsertionSort_StraightInsertionSort {
- public static int[] sis(int[] arr) {
- for (int i = 1; i <arr.length; i++) {
- for (int j = i - 1; j>= 0 && arr[j]> arr[j + 1]; j--) {
- swap(arr, j, j + 1);
- }
- }
- return arr;
- }
- }
1.2 希尔排序
算法思想:
希尔排序的实质就是分组插入排序, 该方法又称为缩小增量排序先将 arr 分割成若干个子序列(由相隔某个增量的元素组成), 分别进行直接插入排序, 然后依次缩小增量再进行排序待整个序列中的元素基本有序(增量足够小时), 再对全体元素进行一次直接插入排序
稳定性:
不稳定
复杂度分析:
TC 最好为 O(N) , 最坏 O(N * N), 平均 TC 为 O(N*1.3)SC 为 O(1)
算法实现:
- public class InsertionSort_ShellSort {
- public static int[] shellSort(int[] arr) {
- for (int gap = arr.length / 2; gap> 0; gap /= 2) {
- for (int i = gap; i <arr.length; i++) {
- for (int j = i - gap; j>= 0 && arr[j]> arr[j + gap]; j -= gap) {
- swap(arr, j, j + gap);
- }
- }
- }
- return arr;
- }
- }
(2)交换排序
2.1 冒泡排序
算法思想:
一次比较两个元素, 如果他们的顺序错误就把他们交换过来
稳定性:
稳定
复杂度分析:
arr 升序时 TC 最好为 O(N) ,arr 降序时 TC 最坏 O(N * N), 平均 TC 为 O(N*N)SC 为 O(1)
算法实现:
- public class Exchange_Bubble {
- public static int[] bubbleSort(int[] arr) {
- for (int i = arr.length; i != 0; i--) {
- for (int j = 1; j <i; j++) {
- if (arr[j] < arr[j - 1]) {
- swap(arr, j - 1, j);
- }
- }
- }
- return arr;
- }
- }
2.2 快速排序
算法思想:
1.先从数列中取出一个数作为基准数;
2.分区过程, 将比这个数大的数全放到它的右边, 小于或等于它的数全放到它的左边;
3.再对左右区间重复第二步, 直到各区间只有一个数
稳定性:
不稳定
复杂度分析:
arr 升序时 TC 最好为 O(NLogN) ,arr 降序时 TC 最坏 O(NLogN), 平均 TC 为 O(NLogN)SC 为 O(1)
算法实现:
- public class Exchange_QuickSort {
- public static int[] quickSort1(int[] arr) {
- return qs1(arr, 0, arr.length - 1);
- }
- private static int[] qs1(int[] arr, int left, int right) {
- if (left> right) {
- return arr;
- }
- int i = left;
- int j = right;
- int tmp = arr[left];
- while (i <j) {
- while (i < j && arr[j]>= tmp) {
- j--;
- }
- while (i <j && arr[i] <= tmp) {
- i++;
- }
- if (i < j) {
- swap(arr, i, j);
- }
- }
- arr[left] = arr[i];
- arr[i] = tmp;
- qs1(arr, left, i - 1);
- qs1(arr, i + 1, right);
- return arr;
- }
- }
(3)选择排序
3.1 简单选择排序
算法思想:
在要排序的一组数中, 选择出最小的数与第一个数交换; 然后在剩下的数中, 选择出最小的数与第二个数交换, 以此类推
稳定性:
不稳定
复杂度分析:
arr 升序时, 只是避免了交换元素的操作, TC 最好仍旧为 O(N*N) ;arr 降序时 TC 最坏 O(N*N), 平均 TC 为 O(N*N)SC 为 O(1)
算法实现:
- public class SelectionSort_SimpleSelectionSort {
- public static int[] simpleSelectionSort(int[] arr) {
- for (int i = 0; i < arr.length; i++) {
- int minIdx = i;
- for (int j = i + 1; j < arr.length; j++) {
- if (arr[j] < arr[minIdx]) {
- minIdx = j;
- }
- }
- if (arr[minIdx] < arr[i]) {
- swap(arr, minIdx, i);
- }
- }
- return arr;
- }
- }
3.2 堆排序
算法思想:
从小到大排序, 构建大顶堆(堆首先是一棵完全二叉树, 大顶堆每个节点的值都不大于父节点的值), 然后每次将堆顶元素和没有排序的最后的元素交换, 重新构建堆(即重新得到最大的堆顶元素)
稳定性:
不稳定
复杂度分析:
最好情况: 如果待排序数组是降序的, 仍然需要 O(N * logN)复杂度的比较操作, 少了移动的操作;
最坏情况: 如果待排序数组是升序的, 不仅需要 O(N * logN)复杂度的比较操作, 而且需要 O(N * logN)复杂度的交换操作总的时间复杂度还是 O(N * logN)
在最好和最坏情况下, 堆排序的时间复杂度都是 O(NlogN)堆排序时, 由于每次重新恢复堆的时间复杂度为 O(logN), 共 N - 1 次堆调整操作, 再加上前面建立堆时 N / 2 次向下调整, 每次调整时间复杂度也为 O(logN)两次次操作时间相加还是 O(N * logN)故堆排序的时间复杂度为 O(N * logN)
堆排序一般优于快速排序的重要一点是, 数据的初始分布情况对堆排序的效率没有大的影响
算法实现:
- public class SelectionSort_HeapSort {
- public static int[] heapSort(int[] arr) {
- buildHeap(arr);
- for (int i = arr.length - 1; i>= 0; i--) {
- swap(arr, 0, i);// 交换完后, 大的元素跑到了数组的后面的部分 所以堆排序时 数组后面到前面逐渐变得有序
- heapify(arr, 0, i); // 调整回大顶堆, 即重新找到未排序部分的最大值
- }
- return arr;
- }
- private static void buildHeap(int[] arr) {
- for (int i = (arr.length - 1) / 2; i>= 0; i--) {
- heapify(arr, i, arr.length);
- }
- }
- // 从 index 开始往下不断调整大顶堆
- private static void heapify(int[] arr, int index, int heapSize) {
- int left = index * 2 + 1;
- int right = index * 2 + 2;
- int largest = index;
- while (left <heapSize) {
- if (arr[left]> arr[index]) {
- largest = left;
- }
- if (right <heapSize && arr[right]> arr[largest]) {
- largest = right;
- }
- if (largest != index) {
- swap(arr, largest, index);
- } else {
- break;
- }
- index = largest;
- left = index * 2 + 1;
- right = index * 2 + 2;
- }
- }
- }
(4)不基于比较的排序
4.1 桶排序
算法思想:
桶排序可用于最大最小值相差较大的数据情况, 要求数据的分布必须均匀, 否则可能导致数据都集中到一个桶中把数组 arr 划分为 n 个大小相同子区间(桶), 每个子区间各自排序, 最后合并计数排序是桶排序的一种特殊情况, 可以把计数排序当成每个桶里只有一个元素的情况
1. 找出待排序数组中的最大值 max 最小值 min;
2. 我们使用 动态数组 ArrayList 作为桶, 桶里放的元素也用 ArrayList 存储桶的数量为(max-min)/arr.length+1;
3. 遍历数组 arr, 计算每个元素 arr[i] 放的桶; 4. 每个桶各自排序; 5. 遍历桶数组, 把排序好的元素放进输出数组
稳定性:
稳定
复杂度分析:
N 个待排数据, M 个桶, 平均每个桶 [N/M] 个数据的桶排序平均时间复杂度为: O(N)+O(M*(N/M)log(N/M))=O(N+N(logN-logM))=O(N+N*logN-N*logM)
当 N=M 时, 即极限情况下每个桶只有一个数据时桶排序的最好效率能够达到 O(N)
桶排序的平均时间复杂度为线性的 O(N+C), 其中 C=N*(logN-logM)如果相对于同样的 N, 桶数量 M 越大, 其效率越高, 最好的时间复杂度达到 O(N)
桶排序的空间复杂度 为 O(N+M), 如果输入数据非常庞大, 而桶的数量也非常多, 则空间代价无疑是昂贵的
算法实现:
- public class NoCompare_BucketSort {
- public static int[] bucketSort(int[] arr) {
- int max = Integer.MIN_VALUE;
- int min = Integer.MAX_VALUE;
- for (int cur : arr) {
- max = Math.max(max, cur);
- min = Math.min(min, cur);
- }
- // 计算桶的数量并构建初始的桶
- int bucketNum = (max - min) / arr.length + 1;
- // int bucketNum = (max - min) + 1; // 每个桶中只有一个元素的时候就是计数排序
- List<List<Integer>> buckets = new ArrayList<>();
- for (int i = 0; i <bucketNum; i++) {
- buckets.add(new ArrayList<>());
- }
- // 将每个元素放到桶中
- for (int cur : arr) {
- int index = (cur - min) / arr.length;
- // int index = (cur - min); // 每个桶中只有一个元素的时候就是计数排序
- buckets.get(index).add(cur);
- }
- // 对每个桶内的元素进行排序, 可以使用直接插入排序等排序方法
- int index = 0;
- for (List<Integer> bucket : buckets) {
- insertSort(bucket);
- for (int cur : bucket) {
- arr[index++] = cur;
- }
- }
- return arr;
- }
- private static void insertSort(List<Integer> bucket) {
- Integer[] arr = bucket.toArray(new Integer[bucket.size()]);
- for (int i = 1; i <arr.length; i++) {
- for (int j = i - 1; j>= 0 && arr[j]> arr[j + 1]; j--) {
- swap(arr, j, j + 1);
- }
- }
- for (int i = 0; i < arr.length; i++) {
- bucket.set(i, arr[i]);
- }
- }
- }
4.2 基数排序
算法思想:
基数排序 (Radix Sort) 是一种非比较型排序算法, 它将整数按位数切割成不同的数字, 然后按每个位分别进行排序
基数排序的方式可以采用 MSD(Most significant digital)或 LSD(Least significant digital),MSD 是从最高有效位开始排序, 而 LSD 是从最低有效位开始排序当然我们可以采用 MSD 方式排序, 按最高有效位进行排序, 将最高有效位相同的放到一堆, 然后再按下一个有效位对每个堆中的数递归地排序, 最后再将结果合并起来但是, 这样会产生很多中间堆 (高位排序比低位排序多了空间开销) 所以, 通常基数排序采用的是 LSD 方式 LSD 基数排序实现的基本思路是将所有待比较数值 (正整数) 统一为同样的数位长度, 数位较短的数前面补零然后, 从最低位开始, 依次进行一次排序这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列
需要注意的是, 对每一个数位进行排序的算法必须是稳定的, 否则就会取消前一次排序的结果
稳定性:
稳定
复杂度分析:
设待排序列为 n 个记录, d 个关键码, 关键码的取值范围为 radix, 则进行链式基数排序的时间复杂度为 O(d(n+radix)), 其中, 一趟分配时间复杂度为 O(n), 一趟收集时间复杂度为 O(radix), 共进行 d 趟分配和收集
空间效率: 需要 2*radix 个指向队列的辅助空间, 以及用于静态链表的 n 个指针
算法实现:
- public class NoCompare_RadixSort {
- public static int[] radixSort(int[] arr) {
- int maxLen = getMaxBit(arr);// 得到 arr 中最大的数的长度
- int[] tmp = new int[arr.length];
- int[] count = new int[10];// 计数器
- int radix = 1;
- for (int i = 1; i <= maxLen; i++) {// 进行 maxLen 次排序
- Arrays.fill(count, 0);// 每次分配前清空计数器
- for (int j = 0; j < arr.length; j++) {
- int k = (arr[j] / radix) % 10;// 统计每个桶中的记录数
- count[k]++;
- }
- for (int j = 1; j < 10; j++) {
- count[j] = count[j - 1] + count[j];// 将 tmp 中的位置依次分配给每个桶
- }
- for (int j = arr.length - 1; j != -1; j--) {// 将所有桶中的记录依次收集到 tmp 中
- int k = (arr[j] / radix) % 10;
- tmp[count[k] - 1] = arr[j];
- count[k]--;
- }
- for (int j = 0; j < arr.length; j++) {// 将临时数组的内容复制到 arr 中
- arr[j] = tmp[j];
- }
- radix = radix * 10;
- }
- return arr;
- }
- // 得到 arr 中最大的数的长度
- private static int getMaxBit(int[] arr) {
- int maxNum = Integer.MIN_VALUE;
- for (int cur : arr) {
- maxNum = Math.max(maxNum, cur);
- }
- return String.valueOf(maxNum).length();
- }
- }
(5)归并排序
算法思想:
将数组分成二组 A,B, 如果这二组组内的数据都是有序的, 那么就可以很方便的将这二组数据进行合并
可以将 A,B 组各自再分成二组依次类推, 当分出来的小组只有一个数据时,
可以认为这个小组组内已经达到了有序, 然后再合并相邻的二个小组就可以了这样通过先递归的分解数列, 再合并数列就完成了归并排序
稳定性:
稳定
复杂度分析:
最好最坏平均 TC 都是 O(NlogN)SC 是 O(N)
算法实现:
- public class MergeSort {
- // 将 arr[first~mid]和 arr[mid~last]合并到 tmp 中
- private static void mergeArray(int[] arr, int first, int mid,
- int last, int[] tmp) {
- int begin1 = first;
- int begin2 = mid + 1;
- int end1 = mid;
- int end2 = last;
- int k = 0;
- while (begin1 <= end1 && begin2 <= end2) {
- if (arr[begin1] < arr[begin2]) {
- tmp[k++] = arr[begin1++];
- } else {
- tmp[k++] = arr[begin2++];
- }
- }
- while (begin1 <= end1) {
- tmp[k++] = arr[begin1++];
- }
- while (begin2 <= end2) {
- tmp[k++] = arr[begin2++];
- }
- // 将辅助数组 tmp 的数据写回 arr
- for (begin1 = 0; begin1 < k; begin1++) {
- arr[first + begin1] = tmp[begin1];
- }
- }
- public static int[] mergeSort(int[] arr, int first,
- int last, int[] tmp) {
- if (first < last) {
- int mid = (first + last) / 2;
- mergeSort(arr, first, mid, tmp);// 左边有序
- mergeSort(arr, mid + 1, last, tmp);// 右边有序
- mergeArray(arr, first, mid, last, tmp);// 将两个有序数列合并
- }
- return arr;
- }
- }
此外, 为了验证结果的正确性, 可以写个和 Arrays.sort()方法比较的代码 getIntArr 得到一个大小是 size, 最大值小于 bound 的 int 数组 arrEquals 比较两个 int 数组是否相等
- public class MyUtil {
- public static int[] getIntArr(int size, int bound) {
- int[] arr = new int[size];
- Random r = new Random();
- for (int i = 0; i < size; i++) {
- arr[i] = r.nextInt(bound);
- }
- return arr;
- }
- public static boolean arrEquals(int[] arr1, int[] arr2) {
- for (int i = 0; i < arr1.length; i++) {
- if (arr1[i] != arr2[i]) {
- return false;
- }
- }
- return true;
- }
- }
以直接插入排序为例, 我们可以这么用 MyUtil
- public static void main(String[] args) {
- int times = 0;
- while (times++ < 100) {
- int[] arr = MyUtil.getIntArr(50, 100);
- int[] brr = arr.clone();
- Arrays.sort(arr);
- if (!MyUtil.arrEquals(arr, sis(brr))) {
- System.out.println("Something Wrong");
- }
- }
- System.out.println("Everything is OK.");
- }
来源: http://www.bubuko.com/infodetail-2544991.html