Gausst松鼠会

这个屌丝很懒，什么也没留下！

热门标签

数据结构八大排序算法，排序只会冒泡排序？进来我教你

作者：Gausst松鼠会 | 2024-04-28 08:17:37

踩

只会冒泡排序

1.插入排序

基本思想：

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为 止，得到一个新的有序序列 。

代码实现：


//直接插入排序
void insert_sort(int* a, int k)
{
for (int i = 0; i < k - 1; i++)
{
	int end = i;
	int tmp = a[end + 1];
	while (end >= 0)
	{
		if (a[end] > tmp)
		{
		   //将前一个数覆盖后一个数
           	a[end + 1] = a[end];
			end--;
		}
		else
		{
			break;
		}
           //将tmp插入到大于或者小于的那个数的后面
		a[end + 1] = tmp;
	}
}
}

直接插入排序总结：

1. 元素集合越接近有序，直接插入排序算法的时间效率越高

2. 时间复杂度： O(N^2)

3. 空间复杂度： O(1) ，它是一种稳定的排序算法

4. 稳定性：稳定

2.希尔排序

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。

从下图可以看出：

gap越大时，大的数更快的跳到后面，但是数据更不接近有序。

gap越小时，大的数跳到后面更慢，但是数据更接近有序。

排序原理如下：

代码实现：


void shell_sort(int* a, int k)
{
int gap = k;
while (gap > 1)
{
	gap = gap / 3 + 1;
	//确定排序次数
	for (int i = 0; i < gap; i++)
	{
		for (int j = i; j < k - gap; j+=gap)
		{
			int end = j;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (a[end] > tmp)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
			}
		}
}
//优化方案
int gap = k;
while (gap > 1)
{
	gap = gap / 3 + 1;
	for (int i = 0; i < k - gap; i++)
	{
		int end = i;
		int tmp = a[end + gap];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + gap] = a[end];
				end -= gap;
			}
			else
			{
				break;
			}
		}
		a[end + gap] = tmp;
	}
}
}

希尔排序特性归纳总结：

1. 希尔排序是对直接插入排序的优化。

2. 当 gap > 1 时都是预排序，目的是让数组更接近于有序。当 gap == 1 时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。

3. 希尔排序的时间复杂度不好计算，因为 gap 的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定。

4. 稳定性：不稳定

3.选择排序

2.2.1 基本思想：

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

将上述选择排序进行优化，依次选出最大值和最小值依次和第一个位置和最后一个位置交换，具体思想如下图：

代码如下：


void select_sort(int* a, int k)
{
int begin = 0, end = k - 1;
while (begin < end)
{
//假设最小值下标和最大值下标为begin位置
	int mini = begin, maxi = begin;
	for (int i = begin+1; i <= end; i++)
	{
		if (a[i] < a[mini])
			mini = i;
		if (a[i] > a[maxi])
			maxi = i;
	}
	swap(a[mini], a[begin]);
//最大值下标在begin位置，但是begin位置的值被最小换走了
//所以最大值就在mini下标的位置
	if (a[maxi]==a[begin])
		maxi = mini;
	swap(a[maxi], a[end]);
	begin++;
	end--;
}
}

4.堆排序

堆排序 (Heapsort) 是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。(如果堆排序有疑问请看我的另外一篇博客，有很详细的堆思想和图解）


void adjust_down(int* a, int parent,int n)
{
int child = parent * 2 + 1;
while (child < n)
{
	//找最大孩子或者最小孩子
	if (child + 1 < n && a[child + 1] > a[child])
		child++;
	if (a[child] > a[parent])
	{
		swap(a[child], a[parent]);
		parent = child;
		child = parent * 2 + 1;
	}
	else
	{
		break;
	}
}
}
 
//堆排序
void heap_sort(int* a, int k)
{
//向下调整法建堆 时间复杂度O(n)
for (int i =(k-1-1)/2; i >=0; i--)
{
	adjust_down(a, i, k);
}
//排序
for (int i = k - 1; i >= 1; i--)
{
	swap(a[0], a[i]);
	adjust_down(a, 0, i);
}
}

堆排序的特性总结：

1. 堆排序使用堆来选数，效率就高了很多。

2. 时间复杂度： O(N*logN)

3. 空间复杂度： O(1)

4. 稳定性：不稳定

5.冒泡排序

基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，冒泡排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

代码如下：


//冒泡排序
void bubble_sort(int* a, int k)
{
for (int i = 0; i < k - 1; i++)
{
	//如果下面没有交换证明已经有序，则中断循环
	int exchange = 0;
	for (int j = 1; j < k - i; j++)
	{
		if (a[j - 1] > a[j])
		{
			swap(a[j - 1], a[j]);
			exchange = 1;
		}
	}
	if (exchange == 0)
	{
		break;
	}
}
}

冒泡排序的特性总结：

1. 冒泡排序是一种非常容易理解的排序

2. 时间复杂度：O(N^2)

3. 空间复杂度：O(1)

4. 稳定性：稳定

6.快速排序

6.1递归实现

快速排序是 Hoare 于 1962 年提出的一种二叉树结构的交换排序方法，其基本思想为： 任取待排序元

素序列中 的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右 子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止 。


// 假设按照升序对array数组中[left, right)区间中的元素进行排序
void QuickSort(int array[], int left, int right)
{
 if(right - left <= 1)
 return;
 
 // 按照基准值对array数组的 [left, right)区间中的元素进行划分
 int div = partion(array, left, right);
 
 // 划分成功后以div为边界形成了左右两部分 [left, div) 和 [div+1, right)
 // 递归排[left, div)
 QuickSort(array, left, div);
 
 // 递归排[div+1, right)
 QuickSort(array, div+1, right);
}

快速排序常见的三种方式：

a. hoare版本

思想如下图：

代码如下：


//hoare单趟排序
int part_sort1(int* a, int left, int right)
{
int keyi = left;
while (left < right)
{
	while (left < right && a[right] >= a[keyi])
	{
		right--;
	}
	while (left < right && a[left] <= a[keyi])
	{
		left++;
	}
	swap(a[left], a[right]);
}
swap(a[keyi], a[left]);
//找到单趟排序的key位置
return left;
}

b. 挖坑法版本

思想如下：

代码如下：


//挖坑法，更易理解
int part_sort2(int* a, int left, int right)
{
int pit = left;
int key = a[left];
while (left<right)
{
	//找小，找到小于key就停下来，填坑
	while (left < right && a[right] >= key)
	//注意：a. 每次结束必须判断left和right关系，防止越界非法访问
	//b. 必须>=否则就会死循环，栗子：(5，5，5）
	{
		right--;
	}
	a[pit] = a[right];
	pit = right;
    //找大，找到大于key就停下来，填坑
	while (left < right && a[left] <= key)
	{
		left++;
	}
	a[pit] = a[left];
	pit = left;
}
//把第一个数key填到pit位置
a[pit] = key;
return pit;
}

c. 双指针法

思想如下：

代码如下：


//双指针法
int part_sort3(int* a, int left, int right)
{
int prev = left;
int cur = left+1;
int key = a[left];
while (cur <=right)
{//找大，遇到小的就停下来交换，遇到大的就往前走
	if (a[cur] < key && (++prev) != cur)
	{
		swap(a[cur], a[prev]);
	}
	cur++;
}
swap(a[prev], a[left]);
return prev;
}

完整的快速排序实现：分治，排完keyi位置，keyi位置保持不变，再使用递归思想排keyi左右两边，[begin,keyi-1] keyi [keyi+1,end]，左边有序右边有序，排序就完成有序。

整趟代码如下：


//快速排序
void quick_sort(int* a, int begin, int end)
{
if (begin >= end)
{
	return;
}
//三数取中，保证二分，降低递归层数
int mid = get_mid_index(a, begin, end);
swap(a[mid], a[begin]);
//小区间优化，防止数据太大，递归层次太深，栈溢出
if ((end - begin) >= 10)
{
	insert_sort(a+begin,end-begin+1);
}
else
{
    //单躺排序
	int keyi = part_sort3(a, begin, end);
    //左边有序
	quick_sort(a, begin, keyi - 1);
    //右边有序
	quick_sort(a, keyi + 1, end);
}
}

优化快速排序：a.三数取中 b.小区间优化

三数取中代码如下：


int get_mid_index(int* a,int begin, int end)
{
int mid = (begin + end) / 2;
if (a[begin] < a[end])
{
	if (a[begin] > a[mid])
		return begin;
	else if (a[mid] > a[end])
		return end;
	else
		return mid;
	}
//a[begin]>a[end]
else
{
	if (a[end] > a[mid])
		return end;
	else if (a[begin] > a[mid])
		return mid;
	else
		return begin;
}
}

6.2 非递归实现

思想如下：

代码如下：


//用一个栈模拟快速排序非递归实现
void quick_sort_nonR(int* a, int begin, int end)
{
stack<int> s;
s.push(end);
s.push(begin);
while (!s.empty())
{
	int begin = s.top();
	s.pop();
	int end = s.top();
	s.pop();
	int  keyi = part_sort1(a, begin, end);
	if (keyi + 1 < end)
	{
		s.push(end);
		s.push(keyi + 1);
	}
	if (begin < keyi - 1)
	{
		s.push(keyi - 1);
		s.push(begin);
	}
}
}

快速排序的特性总结：

1. 时间复杂度：O(N*logN)

2. 空间复杂度：O(logN)

3. 稳定性：不稳定

7.归并排序

7.1递归实现

基本思想：

归并排序（ MERGE-SORT ）是建立在归并操作上的一种有效的排序算法 , 该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。归并排序核心步骤：

代码实现：


//子区间
void _merge_sort(int* a, int begin, int end, int* tmp)
{
//先递归分解,后序
if (begin = end)
{
	return;
}
int mid = (end + begin) / 2;
_merge_sort(a, begin, mid, tmp);
_merge_sort(a, mid + 1, end, tmp);
//归并排序
int begin1 = begin, end1 = mid;
int begin2 = mid + 1,end2 = end;
int i = begin1;
//取俩组区间内小的值依次放在a数组和tmp数组下标对应的位置中
//当一个区间内没有数了，则把另外一个区间内的数依次放入tmp数组中
while (begin1 <= end1 && begin2 <= end2)
{
	if (a[begin1] < a[begin2])
	{
		tmp[i++] = a[begin1++];
	}
	else
	{
		tmp[i++] = a[begin2++];
	}
}
while (begin1 <= end1)
{
	tmp[i++]= a[begin1++];
}
while (begin2 <= end2)
{
	tmp[i++] = a[begin2++];
}
//拷贝tmp数组内数据回原数组a中
memcpy(a + begin, tmp + begin, sizeof(int)*(end-begin+1));
}
 
/归并排序
oid merge_sort(int* a, int begin, int end)
{
int* tmp = new int[end - begin + 1];
_merge_sort(a, begin, end,tmp);
}

7.2非递归实现

思想如下：

但是上述思想只适合于数据个数是2^n，不是2^n的数据会有一定的越界，根据下面代码打印可得：


void merge_sort_nonR(int* a, int begin, int end)
{
int* tmp = new int[end - begin + 1];
int gap = 1;
int n = end - begin + 1;
while (gap < n)
{
	cout << "gap->" << gap << " ";
	for (int i = 0; i < n; i +=2*gap)
	{
		int begin1 = i, end1 = gap+i-1;
		int begin2 = gap + i, end2 = i+2*gap-1;
		printf("[%d,%d]-[%d,%d] ", begin1, end1, begin2, end2);
		int j = begin1;
		while (begin1 <= end1 && begin2 <= end2)
		{
			if (a[begin1] < a[begin2])
			{
				tmp[j++] = a[begin1++];
			}
			else
			{
				tmp[j++] = a[begin2++];
			}
		}
		while (begin1 <= end1)
		{
			tmp[j++] = a[begin1++];
		}
		while (begin2 <= end2)
		{
			tmp[j++] = a[begin2++];
		}
	}
	printf("\n");
	memcpy(a, tmp, sizeof(int) * (n));
	gap *= 2;	
}
}

结果如图所示：

正确代码：


void merge_sort_nonR(int* a, int begin, int end)
{
int n = end - begin + 1;
int* tmp = new int[n];
int gap = 1;
while (gap < n)
{
	cout << "gap->" << gap << " ";
	for (int i = 0; i < n; i +=2*gap)
	{
		int begin1 = i, end1 = gap+i-1;
		int begin2 = gap + i, end2 = i+2*gap-1;
		if (end1 >= n)
		{
			//将end1修回最后一个数的下标位置
			end1 = n - 1;
			//begin2和end2修成不存在的区间
			begin2 = n;
			end2 = n - 1;
		}
		if (begin2 >= n)
		{
			begin2 = n;
			end2 = n - 1;
		}
		if (end2 >= n)
		{
			end2 = n - 1;
		}
		printf("[%d,%d]-[%d,%d] ", begin1, end1, begin2, end2);
		int j = begin1;
		while (begin1 <= end1 && begin2 <= end2)
		{
			if (a[begin1] < a[begin2])
			{
				tmp[j++] = a[begin1++];
			}
			else
			{
				tmp[j++] = a[begin2++];
			}
		}
		while (begin1 <= end1)
		{
			tmp[j++] = a[begin1++];
		}
		while (begin2 <= end2)
		{
			tmp[j++] = a[begin2++];
		}
		//拷贝tmp数组内数据回原数组a中
	}
	printf("\n");
	memcpy(a, tmp, sizeof(int) * (n));
	gap *= 2;
}
}

归并排序的特性总结：

1. 归并的缺点在于需要 O(N) 的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。

2. 时间复杂度： O(N*logN)

3. 空间复杂度： O(N)

4. 稳定性：稳定

8.计数排序

思想：

1. 统计相同元素出现次数 2. 根据统计的结果将序列回收到原来的序列中

看图更清晰：

具体实现请看代码：


//计数排序
void count_sort(int* a, int k)
{
//遍历求数组中的最大和最小值
int max = a[0], min = a[0];
for (int i = 1; i < k; i++)
{
	if (a[i] < min)
		min = a[i];
	if (a[i] > max)
		max = a[i];
}
//求新开辟计数的数组空间大小
int rage = max - min + 1;
int* tmp = new int[rage];
//初始化tmp中的数据为0
memset(tmp, 0, sizeof(int) * rage);
//在tmp数组中计a数组中数据出现的个数
for (int i = 0; i < k; i++)
{
	//相对映射
	tmp[a[i] - min]++;
}
//排序,拷贝数据回原数组中
int i = 0;
for (int j = 0; j < rage; j++)
{
	while (tmp[j]--)
	{
		//回写
		a[i++] = j + min;
	}
}
delete[] tmp;
}

计数排序特性总结：

1. 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。

2. 时间复杂度： O(MAX(N, 范围 ))

3. 空间复杂度： O( 范围 )

4.稳定性：稳定

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Gausst松鼠会/article/detail/501267