/*************************************************************************
 > File Name: sort.cpp
 > Author: SongLee
 ************************************************************************/
#include
using namespace std;

typedef int ElementType;

/*
 *
 * 为了实现N个数的排序，将后面N-1个数依次插入到前面已排好的子序列中，
 *假定刚开始第1个数是一个已排好序的子序列。经过N-1趟就能得到一个有序序列。
 *****时间复杂度：最好情况O(n)，最坏情况O(n^2)，平均情况O(n^2).
 *****空间复杂度：O(1)
 *****稳定性：稳定
 */
void InsertSort(ElementType A[], int n)
{
 int i,j;
 ElementType temp; // 临时变量

 for(i=1; i0 && A[j-1]>temp; --j)
 A[j] = A[j-1];
 A[j] = temp;
 }
}

/*
 *
 * 与直接插入排序不同的是，折半插入排序不是边比较边移动，而是将比较和移
 *动操作分离出来，即先折半查找出元素的待插入位置，然后再统一地移动待插入位
 *置之后的所有元素。不难看出折半插入排序仅仅是减少了比较的次数。
 *****时间复杂度：O(n^2)
 *****空间复杂度：O(1)
 *****稳定性：稳定
 */
void BinaryInsertSort(ElementType A[], int n)
{
 int i, j, low, high, mid;
 ElementType temp;
 for(i=1; i=high+1; --j) // 统一后移
 A[j+1] = A[j];
 A[high+1] = temp; // 插入
 }
}

/*
 *
 * 希尔排序通过比较相距一定间隔的元素，即形如L[i,i+d,i+2d,...i+kd]的序列
 *然后缩小间距，再对各分组序列进行排序。直到只比较相邻元素的最后一趟排序为
 *止，即最后的间距为1。希尔排序有时也叫做*缩小增量排序*
 *****时间复杂度：依赖于增量序列的选择，但最坏情况才为O(N^2)
 *****空间复杂度：O(1)
 *****稳定性：不稳定
 */
void ShellSort(ElementType A[], int n)
{
 int i, j, dk; // dk是增量
 ElementType temp;
 
 for(dk=n/2; dk>0; dk/=2) // 增量变化
 {
 for(i=dk; i=0 && A[j]>temp; j-=dk)
 A[j+dk] = A[j]; // 后移
 A[j+dk] = temp;
 }
 }
}

/*
 *
 * 冒泡排序的基本思想是从后往前（或从前往后）两两比较相邻元素的值，若为
 *逆序，则交换它们，直到序列比较完。我们称它为一趟冒泡。每一趟冒泡都会将一
 *个元素放置到其最终位置上。
 *****时间复杂度：最好情况O(n)，最坏情况O(n^2)，平均情况O(n^2)
 *****空间复杂度：O(1)
 *****稳定性：稳定
 */
void BubbleSort(ElementType A[], int n)
{
 for(int i=0; ii; --j) // 从后往前
 {
 if(A[j-1] > A[j]) 
 {
 flag = true;
 // 交换
 A[j-1] = A[j-1]^A[j];
 A[j] = A[j-1]^A[j];
 A[j-1] = A[j-1]^A[j];
 }
 }

 if(flag == false)
 return;
 }
}

/*
 *
 * 快速排序是对冒泡排序的一种改进。其基本思想是基于分治法：在待排序表L[n]
 *中任取一个元素pivot作为基准，通过一趟排序将序列划分为两部分L[1...K-1]和
 *L[k+1...n]，是的L[1...k-1]中的所有元素都小于pivot，而L[k+1...n]中所有元素
 *都大于或等于pivot。则pivot放在了其最终位置L(k)上。然后，分别递归地对两个子
 *序列重复上述过程，直至每部分内只有一个元素或空为止，即所有元素放在了其最终
 *位置上。
 *****时间复杂度：快排的运行时间与划分是否对称有关，最坏情况O(n^2),最好情况
 *O(nlogn),平均情况为O(nlogn)
 *****空间复杂度：由于需要递归工作栈，最坏情况为O(n)，平均情况为O(logn)
 *****稳定性：不稳定
 */
int Partition(ElementType A[], int low, int high)
{
 // 划分操作有很多版本，这里就总以当前表中第一个元素作为枢纽/基准
 ElementType pivot = A[low];
 while(low < high)
 {
 while(low=pivot)
 --high;
 A[low] = A[high]; // 将比枢纽值小的元素移到左端
 while(low