希尔排序

希尔(shell)排序是插入排序的一种。也称缩小增量排序，是直接插入排序的一种更高效的改进版本。希尔排序是非稳定排序。希尔排序是按照记录下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量减少，每组包含的关键词增多，当增量减少至1时，所有元素被分为1组，算法结束。
我们分割待排序记录的目的是减少待排序记录的个数，并使整个序列向基本有序发展。而如上面这样分完组后，就各自排序的方法达不到我们的要求。因此，我们需要采取跳跃分割的策略：将相距某个“增量”的记录组成一个子序列，这样才能保证在子序列内分别进行直接插入排序后得到的结果是基本有序而不是局部有序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template <typename E>
void inssort(E A[],int n,int incr){
  for(int i = incr;i < n;i += incr){
    for(int j = i;(j > incr) && (A[j] < A[j-incr]);j -= incr)
      swap(A,j,j - incr);
  }
}
template <typename E>
void shellsort(E A[],int n){
  for(int i = n/2;i > 2;i /= 2)//增量从n/2开始，直到增量为2，增量为1的单独处理
    for(int j = 0;j < i;j ++)
      inssort<E>(A[j],n-j,j);//从j处开始,n-j处结束
  inssort<E,Comp>(A,n,1);
}

快速排序

一趟快速排序思想
1、目标：找一个记录，以它的关键字作为枢轴，凡其关键字小于枢轴的记录均移动至该记录之前，反之，凡关键字大于枢轴的记录均移动至该记录之后。致使一趟排序之后，记录的无序序列A[s..t]将分割成两部分：
A[s..i-1]和A[i+1..t]，且A[j].key(左边)≤ A[i].key(枢轴) ≤ A[k].key(右边)
2、首先对无序的记录序列进行“一次划分”，之后分别对分割所得的两个子序列“递归”进行快速排序。
快排1
3、一趟快速排序的过程
a. 首先选定轴，交换轴与最后一个元素；(最后要交换回来)
b. 设定l指针指向第一个元素前的位置，r指向最后元素；
c. 先移动l，遇到比轴大则停止；再移动r，遇到比轴小停止，交换l和r所指元素。
d. 持续执行上一步，直到l和r相遇；
e. 将最后一个元素和停止时l(r)位置的元素交换。

4、代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
template <typename E>
inline int findpivot(E A[],int i,int j)
{ return (i+j)/2; }
/*1、内联函数，编译时直接替换成函数体的内容，避免对栈空间的重复消耗;
2、返回枢轴的下标；取中间、第一个、最后一个都可以。*/
template<typename E>
int partition(E A[],int l,int r,E& pivot){
  do{
    while(A[++l] < pivot);//当左边l所指元素小于枢轴，一直向右寻找，直到大于枢轴，停止
    while((l < r) && A[--r] > pivot);
    swap(A,l,r);
  }while(l < r)
  return l;
}
template<typename E>
void qsort(E A[],int i,int j){//i代表左指针，j代表右指针
  if(j <= i)return ;
  int pivotindex = findpivot(A,i,j);
  /*这里之所以调用函数，是为了后续的可扩展性和修改：
  假如要取第一个元素为枢轴，直接修改findpivot函数即可，
  不用修改qsort函数主体*/
  swap(A,pivotindex,j);//把枢轴放到最后
  int k = partition<E>(A,i-1,j,A[j]);//k为左右指针相遇的地方
  swap(A,k,j);//把枢轴交换回来
  /*把轴交换回位置k，意味着轴把k前后的数据一分为二*/
  qsort<E>(A,i,k-1);
  qsort<E>(A,k+1,j);
}

5、时间复杂度
假设一次划分所得枢轴位置 i=k，则对n个记录进行快排所需时间：
　　　　T(n) = Tpass(n) + T(k-I) + T(n-k),
其中 Tpass(n)为对 n 个记录进行一次划分所需时间。
若待排序列中记录的关键字是随机分布的，则 k 取 1 至 n 中任意一值的可能性相同。
由此可得快速排序所需时间的平均值为：

结论：
快速排序的时间复杂度为O(nlogn)。
若待排记录的初始状态为按关键字有序时，快速排序将蜕化为起泡排序，其时间复杂度为O(n^2)。

合并（归并）排序

算法思想：


例如：

伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
template <tyepname E>
void merge(E A[],E temp[],int left,int right){
  /*合并排序算法虽说也是O(nlogn)，但是使用了临时数组temp，  
  因此STL中的sort()函数一般采用快排(当然还有其他算法的加速)，  
  而非合并排序*/
  if(left == right) return ;
  int mid = (left+right)/2;
  mergesort<E>(A,temp,left,mid);
  mergesort<E>(A,temp,mid+1,right);
  for(int i = left;i <= right;i ++)//将原数组内容复制到临时数组
    temp[i] = A[i];
  int i1 = left,i2 = mid + 1;
  for(int curr = left; curr <= right;curr ++){
    if(i1 == mid + 1)//如果左边的一半已经到头，直接把右边剩下的复制给原数组
      A[curr] = temp[i2++];
    else if(i2 > right)
      A[curr] = temp[i1++];
    else if(temp[i1] < temp[i2])//取小的赋给原数组
      A[curr] = temp[i1++];
    else 
      A[curr] = temp[i2++];
  }
}

时间复杂度：O(nlogn)
时间复杂度：O(n)