首页 > 代码库 > 常见排序介绍

常见排序介绍

直接插入排序

在插入第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))

常见排序介绍