| 常见排序算法及对应的时间复杂度和空间复杂度 | 您所在的位置：网站首页 › 快速排序算法的平均时间复杂度是多少 › 常见排序算法及对应的时间复杂度和空间复杂度 |
常见排序算法及对应的时间复杂度和空间复杂度
|
转载请注明出处： http://blog.csdn.net/gane_cheng/article/details/52652705 http://www.ganecheng.tech/blog/52652705.html （浏览效果更好） 排序算法经过了很长时间的演变，产生了很多种不同的方法。对于初学者来说，对它们进行整理便于理解记忆显得很重要。每种算法都有它特定的使用场合，很难通用。因此，我们很有必要对所有常见的排序算法进行归纳。 排序大的分类可以分为两种：内排序和外排序。在排序过程中，全部记录存放在内存，则称为内排序，如果排序过程中需要使用外存，则称为外排序。下面讲的排序都是属于内排序。 内排序有可以分为以下几类： (1)、插入排序：直接插入排序、二分法插入排序、希尔排序。 (2)、选择排序：直接选择排序、堆排序。 (3)、交换排序：冒泡排序、快速排序。 (4)、归并排序 (5)、基数排序 表格版 排序方法时间复杂度（平均）时间复杂度（最坏)时间复杂度（最好)空间复杂度稳定性复杂性直接插入排序 O(n2) O(n2) O(n) O(1) 稳定简单希尔排序 O(nlog2n) O(n2) O(n) O(1) 不稳定较复杂直接选择排序 O(n2) O(n2) O(n2) O(1) 不稳定简单堆排序 O(nlog2n) O(nlog2n) O(nlog2n) O(1) 不稳定较复杂冒泡排序 O(n2) O(n2) O(n) O(1) 稳定简单快速排序 O(nlog2n) O(n2) O(nlog2n) O(nlog2n) 不稳定较复杂归并排序 O(nlog2n) O(nlog2n) O(nlog2n) O(n) 稳定较复杂基数排序 O(d(n+r)) O(d(n+r)) O(d(n+r)) O(n+r) 稳定较复杂图片版 •思想：每步将一个待排序的记录，按其顺序码大小插入到前面已经排序的字序列的合适位置，直到全部插入排序完为止。 •关键问题：在前面已经排好序的序列中找到合适的插入位置。 •方法： –直接插入排序 –二分插入排序 –希尔排序 (1)直接插入排序（从后向前找到合适位置后插入） 1、基本思想：每步将一个待排序的记录，按其顺序码大小插入到前面已经排序的字序列的合适位置（从后向前找到合适位置后），直到全部插入排序完为止。 2、实例 3、java实现 package DirectInsertSort; public class DirectInsertSort { public static void main(String[] args) { int[] a = { 49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 1 }; System.out.println("排序之前："); for (int i = 0; i < a.length; i++) { System.out.print(a[i] + " "); } // 直接插入排序 for (int i = 1; i < a.length; i++) { // 待插入元素 int temp = a[i]; int j; for (j = i - 1; j >= 0; j--) { // 将大于temp的往后移动一位 if (a[j] > temp) { a[j + 1] = a[j]; } else { break; } } a[j + 1] = temp; } System.out.println(); System.out.println("排序之后："); for (int i = 0; i < a.length; i++) { System.out.print(a[i] + " "); } } }(2)二分法插入排序（按二分法找到合适位置插入） 1、基本思想：二分法插入排序的思想和直接插入一样，只是找合适的插入位置的方式不同，这里是按二分法找到合适的位置，可以减少比较的次数。 2、实例 3、java实现 package BinaryInsertSort; public class BinaryInsertSort { public static void main(String[] args) { int[] a = { 49, 38, 65, 97, 176, 213, 227, 49, 78, 34, 12, 164, 11, 18, 1 }; System.out.println("排序之前："); for (int i = 0; i < a.length; i++) { System.out.print(a[i] + " "); } // 二分插入排序 sort(a); System.out.println(); System.out.println("排序之后："); for (int i = 0; i < a.length; i++) { System.out.print(a[i] + " "); } } private static void sort(int[] a) { for (int i = 0; i < a.length; i++) { int temp = a[i]; int left = 0; int right = i - 1; int mid = 0; while (left = left; j--) { a[j + 1] = a[j]; } if (left != i) { a[left] = temp; } } } }(3)希尔排序 1、基本思想：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2 package ShellSort; public class ShellSort { public static void main(String[] args) { int[] a = { 49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 1 }; System.out.println("排序之前："); for (int i = 0; i < a.length; i++) { System.out.print(a[i] + " "); } // 希尔排序 int d = a.length; while (true) { d = d / 2; for (int x = 0; x < d; x++) { for (int i = x + d; i < a.length; i = i + d) { int temp = a[i]; int j; for (j = i - d; j >= 0 && a[j] > temp; j = j - d) { a[j + d] = a[j]; } a[j + d] = temp; } } if (d == 1) { break; } } System.out.println(); System.out.println("排序之后："); for (int i = 0; i < a.length; i++) { System.out.print(a[i] + " "); } } } ② 选择排序•思想：每趟从待排序的记录序列中选择关键字最小的记录放置到已排序表的最前位置，直到全部排完。 •关键问题：在剩余的待排序记录序列中找到最小关键码记录。 •方法： –直接选择排序 –堆排序 (1)直接选择排序 1、基本思想：在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。 2、实例 3、java实现 package DirectSelectSort; public class DirectSelectSort { public static void main(String[] args) { int[] a = { 49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 1, 8 }; System.out.println("排序之前："); for (int i = 0; i < a.length; i++) { System.out.print(a[i] + " "); } // 直接选择排序 for (int i = 0; i < a.length; i++) { int min = a[i]; int n = i; // 最小数的索引 for (int j = i + 1; j < a.length; j++) { if (a[j] < min) { // 找出最小的数 min = a[j]; n = j; } } a[n] = a[i]; a[i] = min; } System.out.println(); System.out.println("排序之后："); for (int i = 0; i < a.length; i++) { System.out.print(a[i] + " "); } } }(2)堆排序 1、基本思想： 堆排序是一种树形选择排序，是对直接选择排序的有效改进。 堆的定义下：具有n个元素的序列 （h1,h2,…,hn),当且仅当满足（hi>=h2i,hi>=2i+1）或（hi 0) { quickSort(a, 0, a.length - 1); } } private static void quickSort(int[] a, int low, int high) { if (low < high) { // 如果不加这个判断递归会无法退出导致堆栈溢出异常 int middle = getMiddle(a, low, high); quickSort(a, 0, middle - 1); quickSort(a, middle + 1, high); } } private static int getMiddle(int[] a, int low, int high) { int temp = a[low];// 基准元素 while (low < high) { // 找到比基准元素小的元素位置 while (low < high && a[high] >= temp) { high--; } a[low] = a[high]; while (low < high && a[low] |
【本文地址】