本周将会介绍几种常见的排序算法。

简单排序

简单排序是几个简单的排序算法的统称，下面来一一介绍。

冒泡排序

冒泡排序的思想比较直观，每次循环时，会将数组（或链表）内相邻的两个元素进行比较，按照规定的递增（或递减）顺序向后移动，一直到重复到末尾，基本代码如下：

void Bubble_Sort(ElementType A[], int N) {
	for(P=N-1; P>=0; P--) {
		for(i=0; i<P; i++) {
			if(A[i] > A[i+1]) {
				Swap(A[i], A[i+1]);
			}
		}
	}
}

代码框架十分简单，但是这样会有一个问题，那就是待排序列在已经有序的情况下，依然会进行两次循环，尽管不会交换相邻元素的值，但是还是会进行判断，会白白浪费时间。仔细想一下，如果输入序列是有序的，那么元素的值一次也不会交换，根据这个特点，可以对上述的代码进行一点小优化，添加一个标志位，一次有序后就可以直接跳出循环了。具体代码如下：

void Bubble_Sort(ElementType A[], int N) {
	for(P=N-1; P>=0; P--) {
		flag = 0;
		for(i=0; i<P; i++) {
			if(A[i] > A[i+1]) {
				Swap(A[i], A[i+1]);
				flag = 1;
			}
		}
		if(!flag) break;
	}
}

按照上述代码的思路，可以较为清晰的分析出冒泡排序算法的时间复杂度：

最好的情况，序列为顺序序列，$T = O(N)$
最坏的情况，序列为逆序序列，$T = O(N^2)$

另外，对于冒泡排序而言，每一次冒泡结束（内层循环结束一轮）后都会有一个元素被放到这个序列有序后的最终位置上，而且，冒泡排序也不会交换相同元素的位置（使用$>$而不是$\geq$），所以冒泡排序是稳定的排序算法，再者，冒泡排序还有一个优点，即排序的方向是一定的，只会按照一个方向遍历存储数据的数据结构，这是其他排序算法无法达到的。

插入排序

插入排序有个很形象的例子，就是打扑克牌时“理牌”的过程，不过可能有点差别。区别在于，理扑克牌时，手上是没有牌的，而需要理的牌在牌堆里面，也就是说，有两个空间可以放牌，但插入排序实际上只使用了一个内存空间，这样的话，每一次插入时就需要先找到插入的位置了。
按照“理牌”的过程来描述就是：先摸一张牌，从后往前找到合适的插入位置，将比这张牌大的牌向后移（腾出位置），再将新牌插入到这个位置下即可。基本代码如下：

void Insertion_Sort(ElementType A[], int N) {
	for(P=1; P<N; p++) {
		temp = A[P];
		for(i=P; i>0 && A[i-1]>temp; i--) {
			A[i] = A[i-1];
		}
		A[i] = temp;
	}
}

插入排序和冒泡排序的时间复杂度类似：

最好的情况，序列为顺序序列，$T = O(N)$
最坏的情况，序列为逆序序列，$T = O(N^2)$

同时，插入排序也是稳定的排序算法。

时间复杂度下界

对于下标$i < j$，如果$A[i] > A[j]$，则称$(i, j)$是一对**逆序对（Inversion）**如序列${2, 3, 1}$中，$(2, 1)$和$(3, 1)$分别是一对逆序对，逆序对的个数称为逆序数，这与线性代数中的概念是一致的。

在冒泡排序和插入排序中，每次交换位置的两个相邻元素正好消去 1 个逆序对，那么它们的时间复杂度就是：$T(N, I) = O(N+I)$，其中$I$是逆序对的对数。很明显，如果序列基本有序，则$I$值可忽略不计，时间复杂度仅为$T(N)$，此时算法既简单，又高效。

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

由上面的定理，我们可以得出：任何仅以交换相邻两元素来排序的算法，其平均时间复杂度为$\Omega(N^2)$。这意味着，如果想要提高算法的效率，就得在每次交换元素时，不止消去 1 个逆序对，这就要求每次交换的两个元素要在序列中相隔的比较远。

希尔排序

希尔排序的主要目的就是每次交换元素时，通过消去多个逆序对来达到提升算法效率。其主要思想：先定义增量序列$D_M > D_{M-1} > \dots > D_1 = 1$，然后对每个$D_k$进行“$D_k$-间隔”排序（$k=M, M-1, \dots,1$），值得注意的是，后面进行的“间隔”排序不会影响前面“间隔”排序的有序性，也即“$D_k$-间隔”有序的序列，在执行“$D_{k-1}$-间隔”排序后，仍然是“$D_k$-间隔”有序的。
原始希尔排序，增量依次减半，$D_M = \lfloor N/2 \rfloor, D_k = \lfloor D{k+1}/2 \rfloor$，此时最坏情况下的时间复杂度为$T = \Theta(N^2)$，基本代码如下：

void Shell_Sort(ElementType A[], int N) {
	for(D=N/2; D>0; D/=2) {
		for(P=D; P<N; P++) {
			temp = A[P];
			for(i=P; i>=D && A[i-D]>temp; i-=D) {
				A[i] = A[i-D];
			}
			A[i] = temp;
		}
	}
}

在最坏的情况（每次进行间隔排序的序列都是有序的）下，希尔排序会退化成插入排序，原因在于增量元素不互质，则小增量可能根本不起作用。为了解决这个问题，引入了更多的增量序列：

Hibbard增量序列，$D_k = 2^k - 1$，这样保证了相邻增量元素互质，最坏情况下$T = \Omega(N^{3/2})$，猜想$T_{avg} = O(N^{5/4})$
Sedgewick增量序列，${1, 5, 19, 41, 109, \dots}$，也即增量序列的每一个元素是由$9 \times 4^i + 1$或$4^i - 3 \times 2^i + 1$计算得到，猜想$T_{avg} = O(N^{7/6}), T_{worst} = O(N^{4/3})$

由于希尔排序每次对增量序列进行排序，相邻的相等元素属于不同增量序列，则希尔排序可能会改变相等且相邻元素的相对位置，属于不稳定的排序。

选择排序

选择排序是一种简单直观的排序算法，基本工作原理是每一次从待排序的数据元素中选出最小（大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾，重复此过程直到全部待排序的数据元素排完。

简单选择排序

简单选择排序的思路很简单，与选择排序的基本思想一致，基本代码如下：

void Selection_Sort(ElementType A[], int N) {
	for(i=0; i<N; i++) {
	//find the minimum from A[i] to A[n-1], and return to Position
		MinPosition = ScanForMin(A, i, N-1);
	//replace the minimum element to the last position of the ordered part
		Swap(A[i], A[MinPosition]);
	}
}

简单选择排序的时间复杂度主要有两个影响条件，第一个是查找最小值，第二个是交换，所以它的时间复杂度无论怎样都是$T=\Theta(N^2)$。

堆排序

分析了简单选择排序算法的时间复杂度后，发现简单选择排序的时间都耗费在了查找最小值上，如果能把这一操作变快，那么简单选择排序的效率就能提高。根据选择排序的特点，每次查找的值必须是最小（大）值，这与小（大）根堆的性质是一致的，那么使用堆来进行元素的查找，每次弹出最小（大）值，就可以提升排序效率。基本代码如下：

void Heap_Sort(ElementType A[], int N) {
	BuildHeap(A);
	for(i=0; i<N; i++) {
		tempA[i] = DeleteMin[A];
	}
	for(i=0; i<N; i++) {
		A[i] = tempA[i];
	}
}

上述代码的过程比较简单，每次找出最小（大）元素后，保存在一个临时数组内，然后在将临时数组内的排序结果复制到原始数组中。这样即需要额外的空间（$O(N)$）去存储这部分数据，又要额外的时间去复制元素。那么如何去避免这部分开销呢？请看下面的代码：

void Heap_Sort(ElementType A[], int N) {
	for(i=N/2; i>=0; i--) {
		PercDown(A, i, N);	//Build heap
	}
	for(i=N-1; i>0; i--) {
		Swap(&A[0], &A[i]);	//delete max
		PercDown(A, 0, i);
	}
}

按照上述代码，建立一个大根堆，排序开始后，交换大根堆最大元素与最末尾元素的值，完成后，将这个最大值剔除出堆，紧接着再调整为大根堆，重复执行上述操作。

定理：堆排序处理N个不同元素的随机排列的平均比较次数是$2NlogN - O(N log logN)$

虽然堆排序给出最佳平均时间复杂度，但**实际效果不如用Sedgewick增量序列的希尔排序**。

归并排序

归并排序的核心就是有序子列的归并，首先，申请空间，保存合并后的有序序列，设定两个指针，最初位置分别为两个有序序列的起始位置，比较两个指针指向的元素，选择相对小的元素放到申请的空间内，并移动指针到下一位置，重复直至某一个子序列超出序列尾，接着将另一序列剩下的所有元素直接复制到申请空间的尾部。合并两个有序子列的基本代码如下：

void Merge(ElementType A[], ElementType TempA[], int L, int R, int RightEnd) {
	LeftEnd = R-1;	//Suppose two subsequences are side-by-side
	Tmp = L;	//initial position
	NumElements = RightEnd - L + 1;
	while(L <= LeftEnd && R <= RightEnd) {
		if(A[L] <= A[R]) TempA[Tmp++] = A[L++];
		else TempA[Tmp++] = A[R++];
	}
	// copy the rest straightly
	while(L <= LeftEnd) TempA[Tmp++] = A[L++];	
	while(R <= RightEnd) TempA[Tmp++] = A[R++];
	//copy the result to A[] from right to left
	for(i=0; i<NumElements; i++, RightEnd--) {
		A[RightEnd] = TempA[RightEnd]
	}
}

归并算法在实现的时候有两种不同的策略，下面先介绍递归。

递归

归并排序的递归算法的思想是基于分治法的，先将分开的子序列排好，在合并成一个大的序列。基本代码如下：

void MSort(ElementType A[], ElementType TempA[], int L, int RightEnd) {
	int Center;
	if(L < RightEnd) {
		Center = (L + RightEnd)/2;
		MSort(A, TempA, L, Center);
		MSort(A, TempA, Center+1, RightEnd);
		Merge(A, TempA, L, Center+1, RightEnd);
	}
}

基于分治法的归并排序递归算法的时间复杂度为$T(NlogN)$，推导过程如下：
$$
\begin{align} T(N)
& = 2 T(N/2)) + cN \
& = 2\ (2T(N/2^2) + c N/2) + cN \
& = \dots = 2^k * O(1) + ckN \
& = O(NlogN)
\end{align}
$$
可得$T(N) = O(NlogN)$，这个时间复杂度是很“强”的😆，也即是说在任何情况下（无论好坏）都是$NlogN$，另外，归并排序是稳定的排序算法。为了使它与上述其他排序算法的函数接口统一，再整理下代码：

void Merge_Sort_Recursion(ElementType A[], int N) {
	ElementType *TempA;
	TempA = malloc(N*sizeof(ElementType));
	if(TempA != NULL) {
		MSort(A, TempA, 0, N-1);
		free(TempA);
	} else Error("Insufficient Space.");
}

注意在上面的代码中，临时传递使用的数组是声明在Merge_Sort函数中的，这样做的好处就是避免了在MSort中重复声明和重复释放内存操作。

非递归

归并排序的非递归算法基本思想依然是分治法的思想，每次循环先归并相邻的两个子列，子列长度逐渐增加，直至最后左右两个子列之和大于序列总长度。基本代码如下：

void Merge_Sort_Non_Recursion(ElementType A[], int N) {
	int length;
	ElementType *TempA;
	length = 1; //initialize the length of subsequence
	TempA = malloc(N*sizeof(ElementType));
	if(TempA != NULL) {
		while(length < N) {
			Merge_pass(A, TempA, N, length);	//left
			length *= 2;
			Merge_pass(TempA, A, N, length);	//right
			length *= 2;
		}
	} else printf("Insufficient Space.\n");
}

/*Merge adjacent ordered subsequence in pairs accroding to the current 
length of subsequence*/
void Merge_pass(ElementType A[], ElementType TempA[], int N, int length) {
	int i, j;
	for(i=0; i<=N-2*length; i+=length) {
		Merge(A, TempA, i, i+length, i+2*length-1);
	}
	if(i+length < N) {
		//Merge the last two subsequence
		Merge(A, TempA, i, i+length, N-1); 
	} else {
		//only one subsequence last 
		for(j=i; j<N; j++) TempA[j] = A[j];	
	}
}

注意上述代码中的细节，Merge_pass是一个按照序列长度进行一次归并的函数，当序列长度发生变化的时候，将再次调用此函数，另外，在此函数内，for循环内归并的序列是前N/length - 1对，而不是N/length对，如果N是奇数，最后一个子列就被单独出来了，它与其他子列的长度不等，所以针对最后一个子列的处理，要与前面区分开来。再者，上述代码中length增长的倍数是2，理论上即是二路归并。

小结

归并排序算法的优点很明显，那就是在任何情况（无论好坏）下，其时间复杂度都是$T(NlogN)$，同时，它还是稳定的排序算法，但是它有一个很明显的缺点，就是需要占用$O(N)$大小的空间，并且在内存内要频繁的进行倒换操作，所以，一般内部排序中不会使用归并排序，外部排序会使用归并排序。

Homework

09-1 排序

这个题专门用来检测自己实现的排序算法，最好把老师讲了的都实现一下。

冒泡排序

#include <stdio.h>
#include <stdbool.h>
#define maxn 100005
int array[maxn], n;
void swap(int *p1, int *p2) {
	int t = *p1;
	*p1 = *p2;
	*p2 = t;
}
void bubble_sort(int *array, int n) {
	for(int i = n - 1; i > 0; i--) {
		bool flag = true;
		for(int j = 0; j < i; j++) {
			if(array[j] > array[j + 1]){
				swap(&array[j], &array[j + 1]);
				flag = false;
			}
		}
		if(flag) break;
	}
}
int main() {
	scanf("%d", &n);
	for(int i = 0; i < n; i++) {
		scanf("%d", array + i);
	}
	bubble_sort(array, n);
	for(int i = 0; i < n; i++) {
		printf("%d", array[i]);
		if(i < n - 1) putchar(' ');
	}
	return 0;
}

插入排序

#include <stdio.h>
#define maxn 100005
int array[maxn], n;
void insertion_sort(int *array, int n) {
	for(int i = 1; i < n; i++) {
		int tmp = array[i], j;
		for(j = i; j > 0 && tmp < array[j - 1]; j--) {
			array[j] = array[j - 1];
		}
		array[j] = tmp;
	}
}
int main() {
	scanf("%d", &n);
	for(int i = 0; i < n; i++) {
		scanf("%d", array + i);
	}
	insertion_sort(array, n);
	for(int i = 0; i < n; i++) {
		printf("%d", array[i]);
		if(i < n - 1) putchar(' ');
	}
	return 0;
}

希尔排序

#include <stdio.h>
#define maxn 100005
int array[maxn], n;
void insertion_sort(int *array, int n) {
	for(int i = 1; i < n; i++) {
		int tmp = array[i], j;
		for(j = i; j > 0 && tmp < array[j - 1]; j--) {
			array[j] = array[j - 1];
		}
		array[j] = tmp;
	}
}
int main() {
	scanf("%d", &n);
	for(int i = 0; i < n; i++) {
		scanf("%d", array + i);
	}
	insertion_sort(array, n);
	for(int i = 0; i < n; i++) {
		printf("%d", array[i]);
		if(i < n - 1) putchar(' ');
	}
	return 0;
}

堆排序

#include <stdio.h>
#include <stdbool.h>
#define maxn 100005
int array[maxn], n;
void swap(int *p1, int *p2) {
	int t = *p1;
	*p1 = *p2;
	*p2 = t;
}
void Percolatedown(int *heap, int pos, int size) {
	int parent, child, tmp = heap[pos];
	for(parent = pos; parent * 2 + 1 <= size - 1; parent = child) {
		child = parent * 2 + 1;
		if(child != size - 1 && heap[child] < heap[child + 1]) child++;
		if(tmp >= heap[child]) break;
		else heap[parent] = heap[child];
	}
	heap[parent] = tmp;
}
void heap_sort(int *array, int n) {
	for(int i = n / 2 - 1; i >= 0; i--) {
		Percolatedown(array, i, n);
	}
	for(int i = n - 1; i > 0; i--) {
		swap(&array[0], &array[i]);
		Percolatedown(array, 0, i);
	}
}
int main() {
	scanf("%d", &n);
	for(int i = 0; i < n; i++) {
		scanf("%d", array + i);
	}
	heap_sort(array, n);
	for(int i = 0; i < n; i++) {
		printf("%d", array[i]);
		if(i < n - 1) putchar(' ');
	}
	return 0;
}

归并排序

非递归

#include <stdio.h>
#include <stdlib.h>
#define maxn 100005
int array[maxn], n;
void merge(int *array, int *tmparr, int left, int right, int rightend) {
	int leftend = right - 1, tmp = left;
	int numofelements = rightend - left + 1;
	while(left <= leftend && right <= rightend) {
		if(array[left] < array[right]) tmparr[tmp++] = array[left++];
		else tmparr[tmp++] = array[right++];
	}
	while(left <= leftend) tmparr[tmp++] = array[left++];
	while(right <= rightend) tmparr[tmp++] = array[right++];
	for(int i = 0; i < numofelements; i++, rightend--) {
		array[rightend] = tmparr[rightend];
	}
}
void merge_pass(int *array, int *tmparr, int n, int length) {
	int i, j;
	for(i = 0; i <= n - 2 * length; i += (2 * length)) {
		merge(array, tmparr, i, i + length, i + 2 * length - 1);
	}
	if(i + length < n) merge(array, tmparr, i, i + length, n - 1);
	else for(j = i; j < n; j++) tmparr[j] = array[j];
}
void merge_sort(int *array, int n) {
	int *tmparr;
	tmparr = (int*)malloc(n * sizeof(int));
	if(tmparr != NULL) {
		int length = 1;
		while(length < n) {
			merge_pass(array, tmparr, n, length);
			length *= 2;
			merge_pass(tmparr, array, n, length);
			length *= 2;
		}
		free(tmparr);
	} else return;
}
int main() {
	scanf("%d", &n);
	for(int i = 0; i < n; i++) {
		scanf("%d", array + i);
	}
	merge_sort(array, n);
	for(int i = 0; i < n; i++) {
		printf("%d", array[i]);
		if(i < n - 1) putchar(' ');
	}
	return 0;
}

递归

#include <stdio.h>
#include <stdlib.h>
#define maxn 100005
int array[maxn], n;
void merge(int *array, int *tmparr, int left, int right, int rightend) {
	int leftend = right - 1, tmp = left;
	int numofelements = rightend - left + 1;
	while(left <= leftend && right <= rightend) {
		if(array[left] < array[right]) tmparr[tmp++] = array[left++];
		else tmparr[tmp++] = array[right++];
	}
	while(left <= leftend) tmparr[tmp++] = array[left++];
	while(right <= rightend) tmparr[tmp++] = array[right++];
	for(int i = 0; i < numofelements; i++, rightend--) {
		array[rightend] = tmparr[rightend];
	}
}
void msort(int *array, int *tmparr, int left, int rightend) {
	int center;
	if(left < rightend) {
		center = (left + rightend) / 2;
		msort(array, tmparr, left, center);
		msort(array, tmparr, center + 1, rightend);
		merge(array, tmparr, left, center + 1, rightend);
	}
}
void merge_sort(int *array, int n) {
	int *tmparr;
	tmparr = (int*)malloc(n * sizeof(int));
	if(tmparr != NULL) {
		msort(array, tmparr, 0, n - 1);
		free(tmparr);
	} else return;
}
int main() {
	scanf("%d", &n);
	for(int i = 0; i < n; i++) {
		scanf("%d", array + i);
	}
	merge_sort(array, n);
	for(int i = 0; i < n; i++) {
		printf("%d", array[i]);
		if(i < n - 1) putchar(' ');
	}
	return 0;
}

09-2 Insert or Merge

这个题形式简单，但是要想得满分，必须得对插入排序跟归并排序都很了解才行。

题目要求输出两样东西：

判断属于那一种排序
然后输出再进行下一次这种排序后所得的序列

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define maxn 105
int tar[maxn], arr[maxn], tmparr[maxn], n;
bool issame(int *a) {
    for(int i = 0; i < n; i++) {
        if(a[i] != tar[i]) return false;
    }
    return true;
}
void printarray(const int *array, int size) {
    for(int i = 0; i < n; i++) {
        printf("%d", array[i]);
        if(i < n - 1) putchar(' ');
    }
}
void insert_pass(int *array, int pos) {
    int tmp = array[pos], j;
    for(j = pos; j > 0 && tmp < array[j - 1]; j--) {
        array[j] = array[j - 1];
    }
    array[j] = tmp;
}
bool isinsert(int *array, int n, int *round) {
    for(int i = 1; i < n; i++) {
        insert_pass(array, i);
        if(issame(array)) {
            *round = i + 1;
            return true;
        }
    }
    return false;
}
void merge(int *array, int *tmparr, int left, int right, int rightend) {
    int leftend = right - 1, tmp = left;
    int numofelements = rightend - left + 1;
    while(left <= leftend && right <= rightend) {
        if(array[left] < array[right]) tmparr[tmp++] = array[left++];
        else tmparr[tmp++] = array[right++];
    }
    while(left <= leftend) tmparr[tmp++] = array[left++];
    while(right <= rightend) tmparr[tmp++] = array[right++];
    for(int i = 0; i < numofelements; i++, rightend--) {
        array[rightend] = tmparr[rightend];
    }
}
void merge_pass(int *array, int *tmparr, int n, int length) {
    int i, j;
    for(i = 0; i <= n - 2 * length; i += (2 * length)) {
        merge(array, tmparr, i, i + length, i + 2 * length - 1);
    }
    if(i + length < n) merge(array, tmparr, i, i + length, n - 1);
    else for(j = i; j < n; j++) tmparr[j] = array[j];
}
void merge_sort(int *array, int n) {
    int *tmparr;
    tmparr = (int*)malloc(n * sizeof(int));
    if(tmparr != NULL) {
        int length = 1;
        while(length < n) {
            merge_pass(array, tmparr, n, length);
            length *= 2;
            if(issame(tmparr)) {
                merge_pass(tmparr, array, n, length);
                printarray(array, n);
                break;
            }
            merge_pass(tmparr, array, n, length);
            length *= 2;
            if(issame(array)) {
                merge_pass(array, tmparr, n, length);
                printarray(tmparr, n);
                break;
            }
        }
        free(tmparr);
    } else return;
}
int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
        tmparr[i] = arr[i];
    }
    for(int i = 0; i < n; i++) {
        scanf("%d", &tar[i]);
    }
    int round = 0;
    if(isinsert(tmparr, n, &round)) {
        printf("Insertion Sort\n");
        insert_pass(tmparr, round);
        printarray(tmparr, n);
    } else {
        for(int i = 0; i < n; i++) tmparr[i] = arr[i];
        printf("Merge Sort\n");
        merge_sort(tmparr, n);
    }
    return 0;
}

/*
samples:
in:
10
3 1 2 8 7 5 9 4 6 0
1 2 3 7 8 5 9 4 6 0
out:
Insertion Sort
1 2 3 5 7 8 9 4 6 0

in:
10
3 1 2 8 7 5 9 4 0 6
1 3 2 8 5 7 4 9 0 6
out:
Merge Sort
1 2 3 8 4 5 7 9 0 6
*/

09-3 Insertion or Heap Sort

这个题与上题类型一致，只不过把归并排序换成了堆排序。

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define maxn 105
int tar[maxn], arr[maxn], tmparr[maxn], n;
void swap(int *p1, int *p2) {
	int t = *p1;
	*p1 = *p2;
	*p2 = t;
}
bool issame(int *a) {
    for(int i = 0; i < n; i++) {
        if(a[i] != tar[i]) return false;
    }
    return true;
}
void printarray(const int *array, int size) {
    for(int i = 0; i < n; i++) {
        printf("%d", array[i]);
        if(i < n - 1) putchar(' ');
    }
}
void insert_pass(int *array, int pos) {
    int tmp = array[pos], j;
    for(j = pos; j > 0 && tmp < array[j - 1]; j--) {
        array[j] = array[j - 1];
    }
    array[j] = tmp;
}
bool isinsert(int *array, int n, int *round) {
    for(int i = 1; i < n; i++) {
        insert_pass(array, i);
        if(issame(array)) {
            *round = i + 1;
            return true;
        }
    }
    return false;
}
void Percolatedown(int *heap, int pos, int size) {
	int parent, child, tmp = heap[pos];
	for(parent = pos; parent * 2 + 1 <= size - 1; parent = child) {
		child = parent * 2 + 1;
		if(child != size - 1 && heap[child] < heap[child + 1]) child++;
		if(tmp >= heap[child]) break;
		else heap[parent] = heap[child];
	}
	heap[parent] = tmp;
}
void heap_sort(int *array, int n) {
	for(int i = n / 2 - 1; i >= 0; i--) {
		Percolatedown(array, i, n);
	}
	int i;
	for(i = n - 1; i > 0; i--) {
		if(issame(array)) break;
		swap(&array[0], &array[i]);
		Percolatedown(array, 0, i);
	}
	swap(&array[0], &array[i]);
	Percolatedown(array, 0, i);
	printarray(array, n);
}
int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
        tmparr[i] = arr[i];
    }
    for(int i = 0; i < n; i++) {
        scanf("%d", &tar[i]);
    }
    int round = 0;
    if(isinsert(tmparr, n, &round)) {
        printf("Insertion Sort\n");
        insert_pass(tmparr, round);
        printarray(tmparr, n);
    } else {
        for(int i = 0; i < n; i++) tmparr[i] = arr[i];
		printf("Heap Sort\n");
        heap_sort(tmparr, n);
    }
    return 0;
}

/*
samples:
in:
10
3 1 2 8 7 5 9 4 6 0
1 2 3 7 8 5 9 4 6 0
out:
Insertion Sort
1 2 3 5 7 8 9 4 6 0

in:
10
3 1 2 8 7 5 9 4 6 0
6 4 5 1 0 3 2 7 8 9
out:
Heap Sort
5 4 3 1 0 2 6 7 8 9
*/

bachzart's Blog

ZJU_DS_09_排序（上）

简单排序

冒泡排序

插入排序

时间复杂度下界

希尔排序

选择排序

简单选择排序

堆排序

归并排序

递归

非递归

小结

Homework

09-1 排序

冒泡排序

插入排序

希尔排序

堆排序

归并排序

非递归

递归

09-2 Insert or Merge

09-3 Insertion or Heap Sort