直接插入排序

在插入第i个记录的时，R1,R2...已经排好序，这时将关键字R依次与R1...比较，从而找到应该插入的位置，插入位置以及其后的记录依次往后移动。

时间复杂度O(n^2)     空间复杂度O(1)

冒泡排序

首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则交换这两个记录的值，然后比较第二个和第三个记录的关键字，以此类推，知道第n-1个记录和第n个记录比较过为止。上述为第一趟冒泡排序，其结果是关键字最大的记录被交换到第n个记录的位置，然后进行第二趟冒泡排序，对前n-1个记录进行同样的操作，其结果关键字次大的记录被交换到第n-1个记录的位置，最多进行n-1趟，所有的记录有序排列。

时间复杂度O(n^2)     空间复杂度O(1)

简单选择排序

通过n-i在关键字之间比较，从n-i-1个记录中选出关键字最小的记录，并和第i个记录进行交换，当i等于n时所有的记录有序排列

时间复杂度O(n^2)      空间复杂度O(1)

希尔排序

先将真个带排序记录分割成若干个子序列，然后分别进行直接插入排序，带真个序列的记录基本有序时，在对全体记录进行插入排序。

时间复杂度O(n^1.3)     空间复杂度O(1)

快速排序

用一组数组存储记录，附设两个指针i和j，他们的初值分别为指向第一个记录和最后一个记录，设枢纽记录的关键字为pivokey，则首先从j所指向位置起向前搜素，找到第一个关键字小于pivokey的记录与枢纽记录交换，然后从i所指向位置起向后搜索，找到第一个大于关键字pivokey的记录与枢纽记录相互交换，重复这个步骤知道i等于j

时间复杂度O(nlogn)~O(n^2)    空间复杂度O(logn)

堆排序

对一组待排序记录的关键字，首先安装堆的定义排成一个序列，从而可以输出堆顶最大关键字，然后将剩余的关键字再调整新堆，以便得到次打的堆顶。如此反复，指导排成有序序列。

时间复杂度O(nlogn)

归并排序

把n个记录的无序文件看成是由n个长度为1的有序文件组成的文件，然后两两进行归并，得到n/2个长度为2或1的有序文件，再两两归并，如此反复，直到最后形成n个记录的有序文件。

时间复杂度为O(nlogn)

基数排序

按照组成关键字的各个数位的值进行排序，他是分配排序的一种，在在该排序中把关键字K_i看成一个元组。然后一次对各元组低位到高位进行比较，直到最后排序所有的最高位，得到有序序列。

时间复杂度O(d(n+rd))

常见排序介绍