#include <iostream>
#include <stdio.h>
#include <time.h>
#include <sys/timeb.h>
using namespace std;
void print_time(const char * head)
{
struct timeb rawtime;
ftime(&rawtime);
struct tm * timeinfo = localtime(&rawtime.time);
static int ms = rawtime.millitm;
static unsigned long s = rawtime.time;
int out_ms = rawtime.millitm - ms;
unsigned long out_s = rawtime.time - s;
ms = rawtime.millitm;
s = rawtime.time;
if(out_ms < 0)
{
out_ms += 1000;
s -= 1;
}
printf("%s date/time is: %s \tused time is %lu s %d ms.\n", head, asctime(timeinfo), out_s, out_ms);
}
int main()
{
print_time("head");
for (int i = 0; i < 10000000; i++)
;
print_time("tail");
return 0;
}
希尔排序的实质就是分组插入排序，该方法又称缩小增量排序，因DL．Shell于1959年提出而得名。
该方法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。
以n=10的一个数组49, 38, 65, 97, 26, 13, 27, 49, 55, 4为例
第一次： gap = 10 / 2 = 5
49 38 65 97 26 13 27 49 55 4
1A 1B
2A 2B
3A 3B
4A 4B
5A 5B
1A,1B，2A,2B等为分组标记，数字相同的表示在同一组，大写字母表示是该组的第几个元素， 每次对同一组的数据进行直接插入排序。即分成了五组(49, 13) (38, 27) (65, 49) (97, 55) (26, 4)这样每组排序后就变成了(13, 49) (27, 38) (49, 65) (55, 97) (4, 26)，下同。
第二次： gap = 5 / 2 = 2
排序后
13 27 49 55 4 49 38 65 97 26
1A 1B 1C 1D 1E
2A 2B 2C 2D 2E
第三次： gap = 2 / 2 = 1
4 26 13 27 38 49 49 55 97 65
1A 1B 1C 1D 1E 1F 1G 1H 1I 1J
第四次： gap = 1 / 2 = 0 排序完成得到数组
4 13 26 27 38 49 49 55 65 97
#include <iostream>
#include <stdio.h>
using namespace std;
void vPrint(int a[], int n)
{
for (int i = 0; i < n; i++) {
printf("%d ", a[i]);
}
printf("\n");
}
void vInsertSortWithGap(int a[], int n, int gap, int iStartIndex)
{
for (int i = iStartIndex; i < n; i += gap) {
for (int j = i; j >= 0; j -= gap) {
if((j-gap >= 0) && (a[j] < a[j-gap])) {
swap(a[j], a[j-gap]);
}
}
}
}
void shellSort(int a[], int n)
{
for (int gap = n/2; gap > 0; gap /= 2)
{
for (int i = 0; i < gap; i++)
{
vInsertSortWithGap(a, n, gap, i);
}
}
}
int main()
{
int a[] = {5,1,3,4,9,7,6,10,2,8};
vPrint(a, 10);
shellSort(a, 10);
vPrint(a, 10);
return 0;
}
直接选择排序和直接插入排序类似，都将数据分为有序区和无序区，所不同的是直接播放排序是将无序区的第一个元素直接插入到有序区以形成一个更大的有序区，而直接选择排序是从无序区选一个最小的元素直接放到有序区的最后。
设数组为a[0…n-1]。
#include <stdio.h>
#include <iostream>
using namespace std;
void vPrint(int a[], int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}
void selectSort(int a[], int n)
{
int i, j, iMinIndex;
for (i = 0; i < n; i++)
{
iMinIndex = i;
for (j = i + 1; j < n; j++) {
if(a[j] < a[iMinIndex]) {
iMinIndex = j;
}
}
swap(a[i], a[iMinIndex]);
}
}
int main()
{
int a[] = {24,21,132,4531,1,23,352,22,1234,46436};
vPrint(a, 10);
selectSort(a, 10);
vPrint(a, 10);
return 0;
}
强烈推荐«算法导论»，讲的很清楚。
#include <stdio.h>
#include "quicksort.h"
void vSwap(int & iA, int & iB)
{
int iT = iA;
iA = iB;
iB = iT;
}
int iPartition(int a[], int iStart, int iEnd)
{
int iX = a[iEnd];
int iIndex = iStart-1;
for (int i = iStart; i<iEnd; i++)
{
if( a[i] <= iX )
{
iIndex++;
vSwap(a[iIndex], a[i]);
}
}
vSwap(a[iIndex+1], a[iEnd]);
return iIndex+1;
}
void vQuickSort(int a[], int iStart, int iEnd)
{
if(iStart >= iEnd)
{
return ;
}
int iQ = iPartition(a, iStart, iEnd);
vQuickSort(a, iStart, iQ-1);
vQuickSort(a, iQ+1, iEnd);
}
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
首先考虑下如何将将二个有序数列合并。这个非常简单，只要从比较二个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。
#include <iostream>
#include <stdio.h>
using namespace std;
void vPrint(int a[], int n)
{
for (int i = 0; i < n; i++) {
printf("%d ", a[i]);
}
putchar('\n');
}
//merge sorted array a and b into array c
void MergeArray(int a[], int n, int b[], int m, int c[])
{
int i,j,k;
i=j=k=0;
while (i < n && j < m) {
if(a[i] < b[j])
c[k++] = a[i++];
else
c[k++] = b[j++];
}
while (i < n) c[k++] = a[i++];
while (j < m) c[k++] = b[j++];
}
int main()
{
int a[] = {1, 2, 3};
int b[] = {5, 8, 9, 212};
int c[100];
MergeArray(a, 3, b, 4, c);
vPrint(a, 7);
return 0;
}
可以看出合并有序数列的效率是比较高的，可以达到O(n)。
解决了上面的合并有序数列问题，再来看归并排序，其的基本思路就是将数组分成二组A，B，如果这二组组内的数据都是有序的，那么就可以很方便的将这二组数据进行排序。如何让这二组组内数据有序了？
可以将A，B组各自再分成二组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的二个小组就可以了。这样通过先递归的分解数列，再合并数列就完成了归并排序。
#include <iostream>
#include <stdio.h>
using namespace std;
void mergeArray(int a[], int first, int mid, int last, int temp[])
{
int i = first, j = mid + 1;
int m = mid, n = last;
int k = 0;
while (i<=m && j<=n) {
if(a[i] <= a[j]) temp[k++] = a[i++];
else temp[k++] = a[j++];
}
while (i<=m) temp[k++] = a[i++];
while (j<=n) temp[k++] = a[j++];
for (i = 0; i < k; i++)
a[first+i] = temp[i];
}
void mergeSort(int a[], int first, int last, int temp[])
{
if(first < last)
{
int mid = (first+last)/2;
mergeSort(a, first, mid, temp);
mergeSort(a, mid+1, last, temp);
mergeArray(a, first, mid, last, temp);
}
}
bool MergeSort(int a[], int n)
{
int * pi = new int[n];
if(NULL == pi) {
return false;
}
mergeSort(a, 0, n-1, pi);
delete[] pi;
return true;
}
int main()
{
int a[] = {3,2,3421,1234234,1234,12,421,41,434,643,435,355};
MergeSort(a, 12);
for (int i = 0; i < 12; i++) {
printf("%d ", a[i]);
}
printf("\n");
return 0;
}
归并排序的效率是比较高的，设数列长为N，将数列分开成小数列一共要logN步，每步都是一个合并有序数列的过程，时间复杂度可以记为O(N)，故一共为O(NlogN)。因为归并排序每次都是在相邻的数据中进行操作，所以归并排序在O(NlogN)的几种排序方法（快速排序，归并排序，希尔排序，堆排序）也是效率比较高的。
设数组为a[0…n-1]。
//ai[10] = {1,2,3...,8,9,10}; iStart=0, iEnd=10;
void vInsertionSort(int ai[], int iStart, int iEnd)
{
int i = 0;
int j = 0;
int iTemp = 0;
for (i=iStart+1; i<iEnd; i++)
{
for (j=i; j>iStart; j--)
{
if(ai[j] < ai[j-1])
{
iTemp = ai[j];
ai[j] = ai[j-1];
ai[j-1] = iTemp;
}
}
}
}
对数组中的数字 以特定步长排序。
比如：
#include <iostream>
#include <stdio.h>
using namespace std;
void vPrint(int a[], int n)
{
for (int i = 0; i < n; i++) {
printf("%d ", a[i]);
}
printf("\n");
}
/*
* @param a[]: 待排序的数组
* @param n: 数组中数字的个数
* @param gap: 步长
* @param iStartIndex: 开始排序的下标
*/
void vInsertSortWithGap(int a[], int n, int gap, int iStartIndex)
{
for (int i = iStartIndex; i < n; i += gap) {
for (int j = i; j >= 0; j -= gap) {
if((j-gap >= 0) && (a[j] < a[j-gap])) {
swap(a[j], a[j-gap]);
}
}
}
}
int main()
{
int a[] = {5,1,3,4,9,7,6,10,2,8};
vPrint(a, 10);
vInsertSortWithGap(a, 10, 2, 0);
vPrint(a, 10);
return 0;
}
int a[] = {5,1,3,4,9,7,6,10,2,8};
vInsertSortWithGap(a, 10, 1, 0);
输出：1 2 3 4 5 6 7 8 9 10
vInsertSortWithGap(a, 10, 2, 0);
输出：2 1 3 4 5 7 6 10 9 8
vInsertSortWithGap(a, 10, 2, 1);
输出：5 1 3 4 9 7 6 8 2 10
vInsertSortWithGap(a, 10, 3, 0);
输出：4 1 3 5 9 7 6 10 2 8
看懂上面的程序之后，就可以学希尔排序了。