首页 > 代码库 > 直接插入排序、二分插入排序、希尔排序、冒泡排序与简单选择排序

直接插入排序、二分插入排序、希尔排序、冒泡排序与简单选择排序

2024-07-11 02:38:10   214人阅读

一、直接插入排序

稳定，时间复杂度：最好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;
	}
}

五、简单选择排序

不稳定，时间复杂度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

白话经典算法系列之三 希尔排序的实现


联系
我们