一、直接插入排序

稳定，时间复杂度：最好O(n)、最差O(n^2)、平均O(n^2)。空间复杂度O(1)

void InsertSort(int L[], int n)

{

	int i, j,key;

	for (i = 1; i<n; i++)

		if(L[i] < L[i-1])//须要将L[i]插入到有序表L[0...i-1]

		{

			key = L[i];

			for(j = i-1; j >= 0 && key < L[j]; j--)//后移

				L[j+1] = L[j];

			L[j+1] = key;//插入到正确位置

		}

}

二、二分插入排序

查找插入位置时使用二分查找。稳定。最佳情况O(n lg n)，最差和平均情况O(n^2)，空间复杂度O(1)。

void BInsertSort(int L[], int n)

{

	int i, j,key, low, mid, high;

	for (i = 1; i < n; i++)

	{

		key = L[i];

		low = 0; high = i-1;

		while(low <= high)//在有序的L[low,...,high]中折半查找有序插入的位置

		{

			mid = (low+high)/2;

			if(key < L[mid])

				high = mid - 1;

			else

				low = mid + 1;

		}

		for (j = i-1; j>=high+1;j--)//后移	//j >= low

			L[j+1] = L[j];

		L[high+1] = key;//插入key		   //L[low] = key

	}

}

三、希尔排序

不稳定，时间复杂度在理想情况下是O(nlgn)，最坏情况为O(n^2)。空间复杂度O(1)

void ShellSort(int L[], int n)

{

	int gap = n,i, j, tmp;

	int k1=0, k2;

	while (gap > 1)//一趟shell排序

	{

		k1++;k2=0;

		gap = gap/3+1;

		for(i = gap; i < n; i++)

			if(L[i] < L[i-gap])

			{

				k2++;

				tmp = L[i];

				for(j = i-gap;j>=0 && tmp < L[j]; j -= gap)

					L[j+gap] = L[j];

				L[j+gap] = tmp;

				//printf("gap=%d,%d_%d: ",gap,k1, k2);Print(L, n);

			}

	}

}

四、冒泡排序

稳定，时间复杂度最好O(n），最坏和平均情况为O(n^2)。空间复杂度O(1)。

void BubbleSort(int L[], int n)

{

	bool exchange;

	int i, j;

	for(i = 0; i < n; i++)

	{

		exchange = false;

		for(j = n-1; j >i; j--)

			if(L[j] < L[j-1])//这里是小的数往上一直交换

			{

				std::swap(L[j], L[j-1]);

				exchange = true;

			}

		if(!exchange)

			break;

	}

}

双向冒泡排序：

//改进版的冒泡排序(双向冒泡)

void bidBubbleSort(int a[], int n)

{

    int left, right, t, l, r, j, i = 0;

 

    left =0;

    right = n -1;

 

    //双向冒泡算法，极大的降低了循环排序的次数

    while(left < right)

    {

        //必需要给l和r赋值，否则若数组一開始就有序，则right=r中的r未赋值。即报错

        l = left + 1;

        r = right -1;

 

        //第一次循环将最大的值放到末尾

        for(j = left; j < right; j++)

        {

            if(a[j] > a[j + 1])

            {

                t = a[j];

                a[j] = a[j + 1];

                a[j + 1] = t;

                r = j;

            }

        }

        right = r;

 

        //第二次循环将最小的值放到了开头

        for(j = right; j > left; j--)

        {

            if(a[j] < a[j - 1])

            {

                t = a[j];

                a[j] = a[j - 1];

                a[j - 1] = t;

                l = j;

            }

        }

        left = l;

 

        printf("第%d次排序结果：", i + 1);

        i++;

        for(j = 0; j < n; j++){

            printf("%d\t", a[j]);

        }

    }

     printf("终于排序结果： ");

    for(j = 0; j < n; j++){

        printf("%d\t", a[j]);

    }

}

五、简单选择排序

不稳定。时间复杂度O(n^2)。

空间复杂度O(1)。

void SlectSort(int L[], int n)

{

	int i, j, index;

	for(i = 0; i < n-1; i++)

	{

		index = i;

		for(j = i+1; j < n; j++)

			if(L[j] < L[index])

				index = j;

		if(index != i)

			std::swap(L[i], L[index]);

	}

}

參考：http://blog.csdn.net/han_xiaoyang/article/details/12163251#t128

三白话经典算法系列 Shell排序实现