当n比较大，则应该采用复杂度为的排序方法
-
快速排序（平均事件最短）
-
堆排序
-
归并排序
持续比较相邻元素，大的挪到后面，因此大的会逐步往后挪，直到排序不再变化。
平均和最坏情况均为O(n^2)
不断选择剩余元素中的最小值
-
找到数组中最小元素将其和数组第一个元素交换位置
-
在剩下的元素找到最小元素将其与数组第二个元素交换，直到整个数组排序
-
比较次数 =
-
交换次数 = N
-
运行时间与输入无关
-
数据移动最少
通过构建有序序列，对于未排序序列，在已排序序列中从后向前扫描（对于单向链表则只能从前往后遍历），找到相应位置并插入，实现上通常使用in-place排序。
步骤
-
从第一个元素开始，该元素可认为已排序
-
去下一个元素，对已排序的数组从后往前扫描
-
若从排序数组取出的元素大于新元素，则移至下一个位置
-
重复步骤3，直到找到已排序元素小于或等于新元素的位置
-
插入新元素至该位置
-
交换操作和数组中倒置的数量相同
-
最坏情况下需要
N^2/2次比较和N^2/2次交换，最好情况下需要N-1次比较和0次交换。 -
平均情况下需要
N^2/4次比较和N^2/4次交换
将两个有序对数组归并成一个更大的有序数组，通常称为递归排序。这种是一种典型的分治应用。
-
时间复杂度为
-
空间复杂度为O(N)
采用分治思想，大致分为三个步骤
-
定基准：随机选择一个元素作为基准
-
划分区：所有比基准小的元素至于基准左侧，比基准大的元素至于右侧
-
递归调用：递归地调用此切分过程
Two-way partitioning
-
下标_i_和_j_初始化为待排序数组的两端
-
基准元素设置为数组的第一个元素
-
执行
partition操作，大循环内包含两个内循环-
左侧内循环自增_i_，直到遇到不小于基准元素的值为止
-
右侧内循环自减_j_，直到遇到小于基准元素的值为止
-
-
大循环测试两个下标是否相等或交叉，交换其值。
