常见排序算法及对应的时间复杂度和空间复杂度
转载请注明出处：
（浏览效果更好）
排序算法经过了很长时间的演变，产⽣了很多种不同的⽅法。对于初学者来说，对它们进⾏整理便于理解记忆显得很重要。每种算法都有它特定的使⽤场合，很难通⽤。因此，我们很有必要对所有常见的排序算法进⾏归纳。
排序⼤的分类可以分为两种：内排序和外排序。在排序过程中，全部记录存放在内存，则称为内排序，如果排序过程中需要使⽤外存，则称为外排序。下⾯讲的排序都是属于内排序。
内排序有可以分为以下⼏类：
  (1)、插⼊排序：直接插⼊排序、⼆分法插⼊排序、希尔排序。
  (2)、选择排序：直接选择排序、堆排序。
  (3)、交换排序：冒泡排序、快速排序。
  (4)、归并排序
  (5)、基数排序
表格版
排序⽅法时间复杂度（平均）时间复杂度（最坏)时间复杂度（最好)空间复杂度稳定性复杂性
直接插⼊排序O(n2)O(n2)O(n2)O(n2)O(n)O(n)O(1)O(1)稳定简单
希尔排序O(nlog2n)O(nlog2n)O(n2)O(n2)O(n)O(n)O(1)O(1)不稳定较复杂
直接选择排序O(n2)O(n2)O(n2)O(n2)O(n2)O(n2)O(1)O(1)不稳定简单堆排序O(nlog2n)O(nlog2n)O(nlog2n)O(nlog2n)O(nlog2n)O(nlog2n)O(1)O(1)不稳定较复杂
冒泡排序O(n2)O(n2)O(n2)O(n2)O(n)O(n)O(1)O(1)稳定简单
快速排序O(nlog2n)O(nlog2n)O(n2)O(n2)O(nlog2n)O(nlog2n)O(nlog2n)O(nlog2n)不稳定较复杂
归并排序O(nlog2n)O(nlog2n)O(nlog2n)O(nlog2n)O(nlog2n)O(nlog2n)O(n)O(n)稳定较复杂
基数排序O(d(n+r))O(d(n+r))O(d(n+r))O(d(n+r))O(d(n+r))O(d(n+r))O(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 <= right)
{
mid = (left + right) / 2;
if (temp < a[mid])
{
right = mid - 1;
}
else
{
left = mid + 1;
}
}
用sort outfor (int j = i - 1; j >= 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<=h2i,hi<
=2i+1） (i=1,2,…,n/2)时称之为堆。在这⾥只讨论满⾜前者条件的堆。由堆的定义可以看出，堆顶元素（即第⼀个元素）必为最⼤项（⼤顶堆）。完全⼆叉树可以很直观地表⽰堆的结构。堆顶为根，其它为左⼦树、右⼦树。
  思想：初始时把要排序的数的序列看作是⼀棵顺序存储的⼆叉树，调整它们的存储序，使之成为⼀个堆，这时堆的根节点的数最⼤。然后将根节点与堆的最后⼀个节点交换。然后对前⾯(n-1)个数重新调整使之成为堆。依此类推，直到只有两个节点的堆，并对它们作交换，最后得到有n个节点的有序序列。从算法描述来看，堆排序需要两个过程，⼀是建⽴堆，⼆是堆顶与堆的最后⼀个元素交换位置。所以堆排序有两个函数组成。⼀是建堆的渗透函数，⼆是反复调⽤渗透函数实现排序的函数。
2、实例
初始序列：46,79,56,38,40,84
建堆：
交换，从堆中踢出最⼤数

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。