排序算法根据是否需要访问外存,分为内部排序和外部排序。

内部排序是指待排序列完全存放在内存中所进行的排序过程,适合不太大的元素序列。

外部排序是指大文件的排序,即待排序的记录存储在外存储器上,待排序的文件无法一次装入内存,需要在内存和外部存储器之间进行多次数据交换,来达到排序整个文件的目的。

基本思想:对相邻的元素进行两两比较,顺序相反则进行交换。每一趟排序都会将最小或最大的元素放置待排数组的末尾,最终达到完全有序。

第三趟排序结果:1、2、3、4

最终排序结果为:1、2、3、4

选择一个基准元素,通常选择第一个元素或最后一个元素。

通过一趟排序将待排元素分为两部分,一部分元素小于基准元素,另一部分元素大于基准元素。

此时,基准元素在处于最终序列的正确位置。分别对这两部分使用同样的方法进行排序,直至整个序列有序。

时间复杂度为O(n*logn),当数据有小到大或由大到小排列时,快速排序的效率最低,时间复杂度为O(n^2)

选择第一个元素作为基准相对简单,但当其为最大或最小值时,快速排序的效率会降低。这时,采用“三项取中法”来避免最值情况出现。