- 基本算法（下）
- 一、选择排序
- 二、插入排序
- 三、归并排序(Bottom-Up Merge Sorting)
- 四、基数排序(Radix Sort)
基本算法（下） 一、选择排序
选择排序过程：
算法伪代码如下：
Input:A[1..n] Output:已排好序的A[1...n] for i = 1 to n: k = i//记录位置 for j = i+1 to n://从后面的找最小 if A[j] < A[k]: k = j//记录位置 t = A[i]//交换 A[i] = A[k] A[k] = t
对于长度为n的数组，算法的比较次数为:(n-1)+(n-2)+(n-3)+…+1=n(n-1)/2；算法的元素赋值次数为：0~3(n-1)，因为在交换元素的时候要赋值三次；算法的时间复杂度为：O( n 2 n^2 n2)。
递归实现：
Input:A[1..n] Output:已排好序的A[1...n] sort(i) def sort(i): if i < n : k = i//记录位置 for j = i+1 to n://从后面的找最小 if A[j] < A[k]: k = j//记录位置 t = A[i]//交换 A[i] = A[k] A[k] = t sort(i+1)二、插入排序
插入排序过程：
整体思路：
在待排序的元素中，假设前n-1个元素已有序，现将第n个元素插入到前面已经排好的序列中，使得前n个元素有序。按照此法对所有元素进行插入，直到整个序列有序。
但我们并不能确定待排元素中究竟哪一部分是有序的，所以我们一开始只能认为第一个元素是有序的，依次将其后面的元素插入到这个有序序列中来，直到整个序列有序为止。
算法伪代码如下：
Input:A[1..n] Output:已排好序的A[1...n] sort(n) def sort(i): if i > 0 : sort(i-1) x = A[i]//每次前k个数都是有序的 j = i - 1 while(A[j]>x & j>0)://找谁比x小 A[j+1] = A[j] j = j - 1 A[j+1] = x
对于长度为n的数组，算法的比较次数介于n-1~n*(n-1)/2之间，分别对应升序和降序的情况；算法的赋值次数为比较次数+n-1，即每次比较后的移动操作都要对元素进行赋值，最后插入的过程也要进行赋值。
算法的时间复杂度：最坏情况下为O(N*N)，此时待排序列为逆序，或者说接近逆序；最好情况下为O(N)，此时待排序列为升序，或者说接近升序。
递归实现：
Input:A[1..n] Output:已排好序的A[1...n] for i = 2 to n: x = A[i]//每次前k个数都是有序的 j = i - 1 while(A[j]>x & j>0)://找谁比x小 A[j+1] = A[j] j = j - 1 A[j+1] = x三、归并排序(Bottom-Up Merge Sorting) 四、基数排序(Radix Sort)
输入：{53, 3, 542, 748, 14, 214}
第一次迭代：542，53，3，14，214，748
第二次迭代：3，14，214，542，748，53
第三次迭代：3，14，53，214，542，748
算法伪代码如下：
Input:A linked list of numbers L = {a1,a2,a3,...,ak} and the number of digits k
Output:升序表L
for i = 1 to k:
prepare 10 empty list L0,...,L9
for j in L:
append j to Li
L = L0
for k = 1 to 9:
append Lk to L
return L
可以确定基数排序的时间复杂度一定是线性级别的,但是虽然是线性级别的,但是有一个系数的,这个系数就是最大元素的位数K,所以时间复杂度应该是O(n*k)，如果k是常数，则为O(n)；空间复杂度为：O(10×n)= O(n)。
