c语言中四种排序方法的优劣?
快速排序(QuickSort)
快速排序是一个就地排序,分而治之,大规模递归的算法。从本质上来说,它是归并排序的就地版本。快速排序可以由下面四步组成。
(1) 如果不多于1个数据,直接返回。
(2) 一般选择序列最左边的值作为支点数据。
(3) 将序列分成2部分,一部分都大于支点数据,另外一部分都小于支点数据。
(4) 对两边利用递归排序数列。
快速排序比大部分排序算法都要快。尽管我们可以在某些特殊的情况下写出比快速排序快的算法,但是就通常情况而言,没有比它更快的了。快速排序是递归的,对于内存非常有限的机器来说,它不是一个好的选择。
2 归并排序(MergeSort
归并排序先分解要排序的序列,从1分成2,2分成4,依次分解,当分解到只有1个一组的时候,就可以排序这些分组,然后依次合并回原来的序列中,这样就可以排序所有数据。合并排序比堆排序稍微快一点,但是需要比堆排序多一倍的内存空间,因为它需要一个额外的数组。
3 堆排序(HeapSort)
堆排序适合于数据量非常大的场合(百万数据)。
堆排序不需要大量的递归或者多维的暂存数组。这对于数据量非常巨大的序列是合适的。比如超过数百万条记录,因为快速排序,归并排序都使用递归来设计算法,在数据量非常大的时候,可能会发生堆栈溢出错误。
堆排序会将所有的数据建成一个堆,最大的数据在堆顶,然后将堆顶数据和序列的最后一个数据交换。接下来再次重建堆,交换数据,依次下去,就可以排序所有的数据。
C语言插入排序与选择排序的区别?
区别一:
选择排序的时间复杂度是定死的,就是O(n^2),与数据的输入状态无关。因为对于选择排序,当我们从乱序的区间中找极值时,总是一味的去遍历这个乱序的区间,直到乱序的区间遍历完成后,我们才能确定极值。
插入排序的时间复杂度与数据的输入有关,当初始时给你的数据就是有序的,那么这种状态就是插入排序最好的情况,时间复杂度为O(n),因为对于当前要插入的数x1来说,我们在从后往前遍历乱序区间时,只要找到了x1应该待的位置,就不用在遍历乱序区间中剩下的元素了,那么对于这种最好的情况,我们每次进行乱序区间遍历操作的时间复杂度就会是O(1),一共进行n次乱序区间的遍历操作,总的时间复杂度为O(n)。
从另一个方面来看,我们认为插入排序比选择排序更加聪明,因为插入排序不会做多余的工作,而选择排序会把所有的工作都做完。
区别二:
选择排序是脱机的排序算法,何为脱机算法,就是必须一次性把数据全部给你后,你这个算法才能够执行,而对于选择排序来说,就是脱机的,必须把所有的数据全部给你后,你才能进行选择排序。
主要区别如下:
首先,插入排序选定当前排序位置后,是和前面的有序列(有序列就是前面已经排好序的)进行比较排序;而选择排序是当前排序位置和后面的无序列(就是剩下的还没有排序的)进行排序比较的。
其次,插入排序是前面有序列两两进行位置交换,而选择排序是当前位置和找到的目标位置直接进行交换(可谓一步到位)。

