「レ: 从零开始的带学数据结构㊂」排序算法初学

新的一步。按道理来说我们学校那个 DSA 应该可以不挂科了。想不到期末机考只考了一个树的重构，令人感叹。

「レ: 从零开始的带学数据结构㊂」排序算法初学

冒泡排序和插入排序

默认顺序从小到大的代码实现：

template <typename T> class Sort	
{
    public:
	void Bubble_Sort(T Data[], int N)
    {
        for(int i = 0; i < N - 1; i++){
            bool flag = false;

            for(int j = 0; j < N - i - 1; j++){
                if(Data[j] >= Data[j + 1])
                    T Temp = Data[j];
                    Data[j] = Data[j + 1]; 
                    Data[j + 1] = Temp;
                    flag = true;
            }
            if(!flag)
                break;
        }
    }

    void Insertion_Sort(T Data[], int N) //打牌
    {
        for(int i = 1; i < N; i++)
        {
            T Temp = Data[i];
            for(int j = i; j > 0 && Data[j - 1] > Temp;/*顺序是反的*/ j--)
                Data[j] = Data[j - 1];  //找到合适的位置，移出空位。
            Data[j] = Temp;
        }
    }
};

时间复杂度最好是 O(n)，最差是O(n^2)。每次交换元素都会消除一个逆序对，而定理说明：

任意 N 个不同元素组成的序列平均具有 N*(N-1)/4个逆序对。

所以任何仅以交换相邻两元素来排序的算法，其平均时间复杂度为Ω(N^2)。

为了提高效率，每次消去不只一个元素，需要到相隔较远的位置进行处理。

希尔排序

ＩＩＩＩＰＩＩＩＩＰ 5-序列

ＩＩＰＩＩＰＩＩＰＩ 3-序列

定义增量序列Dm > Dm-1 > ... > D1 = 1

对每个 Dk 进行「Dk- 间隔」排序（k = M, M-1...1）

注意到这个过程中，每次间隔排序后，上一次的间隔仍旧可以保留。也就是说，「Dk- 间隔」有序的序列，在进行「Dk-1 - 间隔」排序后，仍然是「Dk- 间隔」有序的。

原始的 ShellSort 的增量数列是一个等比数列。 K, 1/2K, 1/4K….1。但是由于增量不互质，时间复杂度还是 O(n^2)。Sedgewick 等人提出了不同的增量序列，但时间复杂度还是难以证明。

代码实现：

void Original_Shell_sort(T Data[], int N)
   {
       for(int D = N/2; D > 0; D/=2)   //增量序列。
       {
           for(int i = D; i < N; i++)
           {
               T Temp = Data[i];
               for(j = i; j >= D && Data[j - D] > Temp; j -= D)
                   Data[j] = Data[j - D];
               Data[j] = Temp;
           }
       }
   }

选择排序和堆排序

选择排序的代码实现：

void Selection_Sort(T Data[], int N)
{
    for(int i = 0; i < N; i++)
        MinPosition = ScanForMin(Data, i, N-1);
    	Swap()
}

归并排序（分治法）

归并排序的核心操作是归并。~~这不是废话吗~~ 首先先从有序子列的归并开始考虑情况。先比一下两个子列指针的元素哪个小，把小的先放进去；然后继续这样比较，每次把更小的那个放进去。有 N 个元素，时间复杂度就是 O（N）。

归并操作的伪代码实现：

Merge(A[], TempA[], L, R, RightEnd)	//L, R 代表两个子列的指针。RightEnd 是右面的终点。
	LeftEnd <- R - 1	//假设左右两个子列连续存储。
	Temp <- L	//Temp 表示一个指针，存放结果的初始位置。
	Amount <- RightEnd - L + 1	//元素数量
	
	while (L <= LeftEnd && R <= RightEnd):
		if(A[L] <= A[R]):
			TempA[Temp] <- A[L]
			Temp++	L++
		else:
			TempA[Temp] <- A[R]
			Temp++	R++
	
	while (L <= LeftEnd):	//右子列已经被榨干了ww
		TempA[Temp] <- A[L]
		Temp++	L++
	
	while (R <= RightEnd):
		TempA[Temp] <- A[R]
		Temp++	R++
		
	for( i 从 [0, Amount) ++, RightEnd--)	A[RightEnd] = TempA[RightEnd] //把归并完的结果还回来。

假设代排的序列放在数组里面，递归地把左右分别排好序，然后调用上面的算法，就是归并排序的流程。（分治法）

MergeSort(A[], TempA[], L, RightEnd)
	if (L < RightEnd):	//递归基是 L = Rightend。当只有一个元素的时候停止分治。
		Center = (L + RightEnd) / 2
		MergeSort(A, TempA, L, Center)
		MergeSort(A, TempA, Center + 1, RightEnd)
		Merge(A, TempA, L, Center + 1, RightEnd)

快速排序（分治法）

原理：在一系列元素中选出一个主元，分出左右两个独立子集，分别小于它和大于它；递归的不断选出主元，直到子集合中只有一个元素为止。

伪代码实现：

Quicksort(A[], N)
	if N < 2: return
	pivot <- A[]	//选择主元
	把 S = {A[] \ pivot} 分成两个独立子集
		A1 <- {a∈S | a <= pivot}
		A2 <- {a∈S | a >= pivot}
	A[] = Quicksort(A1, N1) ∪ {pivot} ∪ Quicksort(A2, N2)