欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

排序算法——选择,插入,冒泡,希尔,快排,归并

程序员文章站 2022-06-04 15:08:19
...

1.选择排序

思想:从所有待排元素中选择最小元素

void SelectionSort(int array[], int len) // O(n*n)
{
	int i = 0;
	int j = 0;
	int k = -1;

	for(i=0; i<len; i++)
	{
		k = i; //寻找最小元素的下标
		for(j=i+1; j<len; j++)
		{
			if( array[j] < array[k] ) //开始寻找最小元素的下标
			{
				k = j;	
			}
		}
		swap01(array, i, k);
	}
}

2.插入排序

插入排序就是整理扑克。

思想:(1)空出空位(2)移动位置,找到插入位置

void InertionSort(int array[], int len) // O(n*n)
{
	int i = 0;
	int j = 0;
	int k = -1;
	int temp = -1;

	//{12, 5, 433, 253, 216, 7};
	for(i=1; i<len; i++)
	{
		k = i; //待插入位置
		temp = array[k];

		for(j=i-1; (j>=0) && (array[j]>temp); j--)
		{ 
			array[j+1] = array[j]; //元素后移
			k = j; //k需要插入的位置
		}
		array[k] = temp;//元素插入
	}
}

3.冒泡排序

思想:相邻元素比较,符合条件就交换

冒泡改进,加了exchange,如果已经排好序了,就不需要执行完全部操作。

void BubbleSort(int array[], int len) // O(n*n)
{
	int i = 0;
	int j = 0;
	int exchange = 1; //表明数组是否已经排好序 已经排好序为0   1表示没有排好序
	for(i=0; (i<len) && exchange; i++)
	{
		exchange = 0;//认为已经排序完毕
		for(j=len-1; j>i; j--)
		{
			if( array[j] < array[j-1] )
			{
				swap03(array, j, j-1);
				exchange = 1;//
			}
		}
	}
}

4.希尔排序

思想:插入排序+分组

特点:效率突破n*n,但是由于分组,所以不稳定。

排序算法——选择,插入,冒泡,希尔,快排,归并

//nlogn
void ShellSort(int array[], int len) //
{
	int i = 0;
	int j = 0;
	int k = -1;
	int temp = -1;
	int gap = len;
	do
	{
		 //业界统一实验的 平均最好情况 经过若干次后,收敛为1
		gap = gap / 3 + 1; //gap /2345 2000 都行  //O(n 1.3)
	
		for(i=gap; i<len; i++)    //通过 i++,实现对所有组进行插入排序
		{
			if(array[i - gap] < array[i])
				continue;
			k = i;
			temp = array[k];

			for(j=i-gap; (j>=0) && (array[j]>t
			{
				array[j+gap] = array[j];
				k = j;
			}

			array[k] = temp;
		}

	}while( gap > 1 );

}

5.快速排序

思想:递归+找中

特点:(1)突破n*n(2)进行分组,所以不稳定

排序算法——选择,插入,冒泡,希尔,快排,归并


下面是找中轴的方法:

排序算法——选择,插入,冒泡,希尔,快排,归并


int partition(int array[], int low, int high)
{
	int pv = array[low];

	while( low < high )
	{
		while( (low < high) && (array[high] >= pv) )
		{
			high--; //比基准大,本来就在右边,所以high前移动
		}
		swap5(array, low, high);
		while( (low < high) && (array[low] <= pv) )
		{
			low++;
		}
		swap5(array, low, high);
	}
	//返回枢轴的位置。。。重要
	return low;
}
void QSort(int array[], int low, int high)
{
	if( low < high )
	{
		int pivot = partition(array, low, high);

		//对子序列1排序
		QSort(array, low, pivot-1);
		//对子序列2排序
		QSort(array, pivot+1, high);
	}
}

void QuickSort(int array[], int len) // O(n*logn)
{
	QSort(array, 0, len-1);
}

6.归并排序

思想:(1)将无序序列变成单元素序列(有序序列)(2)两个有序序列合并成一个有序序列

特点:(1)突破n*n(2)稳定(3)以空间换时间

void Merge(int src[], int des[], int low, int mid, int high)
{
	int i = low;
	int j = mid + 1;
	int k = low;

	while( (i <= mid) && (j <= high) ) //将小的放到目的地中
	{
		if( src[i] < src[j] )
		{
			des[k++] = src[i++];
		}
		else
		{
			des[k++] = src[j++];
		}
	}

	while( i <= mid )  //若还剩几个尾部元素
	{
		des[k++] = src[i++];
	}

	while( j <= high ) //若还剩几个尾部元素
	{
		des[k++] = src[j++];
	}
}

//每次分为两路 当只剩下一个元素时,就不需要在划分
void MSort(int src[], int des[], int low, int high, int max)
{
	if( low == high ) //只有一个元素,不需要归并,结果赋给des[low]
	{
		des[low] = src[low]; 
	}
	else //如果多个元素,进行两路划分
	{
		int mid = (low + high) / 2;
		int* space = (int*)malloc(sizeof(int) * max);

		//递归进行两路,两路的划分 
		//当剩下一个元素的时,递归划分结束,然后开始merge归并操作
		if( space != NULL )
		{
			MSort(src, space, low, mid, max); 
			MSort(src, space, mid+1, high, max);
			Merge(space, des, low, mid, high); //调用归并函数进行归并
		}

		free(space);
	}
}

void MergeSort(int array[], int len) // O(n*logn)
{
	MSort(array, array, 0, len-1, len);
}


算法总结:

排序算法——选择,插入,冒泡,希尔,快排,归并