【算法篇C++实现】常见排序算法

这篇具有很好参考价值的文章主要介绍了【算法篇C++实现】常见排序算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


🚀一、选择排序

算法精炼每趟从待排序的记录中选出关键字最小的记录,顺序放在已排序的记录序列末尾,直到全部排序结束为止。

简单排序处理流程

  1. 从待排序序列中,找到关键字最小的元素;
  2. 如果最小元素不是待排序序列的第一个元素,将其和第一个元素互换;
  3. 从余下的 N - 1 个元素中,找出关键字最小的元素,重复1、2步,直到排序结束。

或者:

  1. 从待排序序列中,找到关键字最大的元素;
  2. 如果最大元素不是待排序序列的最后一个元素,将其和最后一个元素互换;
  3. 从余下的 N - 1 个元素中,找出关键字最大的元素,重复1、2步,直到排序结束。

【算法篇C++实现】常见排序算法,数据结构与算法,算法,排序算法,c++

时间复杂度:

  • 简单选择排序的比较次数与序列的初始排序无关。 假设待排序的序列有 N 个元素,第一个元素和后面每个元素比较(n-1次),将最小的排在前面,再将第二个元素和后面每个元素比较(n-2次),则可以近似地表示为 (n-1) + (n-2) + … + 1。这是一个等差数列的求和,可以使用等差数列求和公式进行计算。比较次数总是N (N - 1) / 2。
  • 所以,综合以上,简单排序的时间复杂度为 O(N^2)

C语言代码实现:文章来源地址https://www.toymoban.com/news/detail-646170.html

 #include <stdio.h>
//最小值往前放
void SelectSort(int arr[], int len)
{
	if (len < 1 || arr == nullptr) return;
 
	for (int i = 0; i < len; i++)
	{
		int minindex = i;//用来保存最小值的索引
		for (int j = i + 1; j < len; j++)
		{
			if (arr[j] < arr[index])
			{
				index = j;
			}
		}
		int temp = arr[i];
		arr[i] = arr[index];
		arr[index] = temp;
	}
}
//最大值往后放
void SelectSort1(int arr[], int len)
{
	if (len < 1 || arr == nullptr) return;
 
	for (int i = len-1; i > 0; --i)
	{
		int index = i;//用来保存最大值的索引
		for (int j = 0; j < i; j++)
		{
			if (arr[j] > arr[index])
			{
				index = j;
			}
		}
		int temp = arr[index];
         arr[index] = arr[i];
         arr[i] = temp;
        }
	}
}

void PrintAddr(int arr[], int len)
{
	for (int i = 0; i < len; i++)
		printf("%d ", arr[i]);
	printf("\n");
}
int main()
{
	int arr[] = { 9,1,2,5,7,4,8,6,3,5 };
	int len = sizeof(arr) / sizeof(arr[0]);
	SelectSort(arr, len);
	PrintAddr(arr, len);
}

🚀二、冒泡排序

算法精炼依次比较相邻的两个数,将比较小的数放在前面,比较大的数放在后面。

处理流程

  1. 第一次比较:首先比较第一和第二个数,将小数放在前面,将大数放在后面。
  2. 比较第2和第3个数,将小数 放在前面,大数放在后面。…
  3. 如此继续,直到比较到最后的两个数,将小数放在前面,大数放在后面,重复步骤,直至全部排序完成
  4. 在上面一趟比较完成后,最后一个数一定是数组中最大的一个数,所以在比较第二趟的时候,最后一个数是不参加比较的。
  5. 在第二趟比较完成后,倒数第二个数也一定是数组中倒数第二大数,所以在第三趟的比较中,最后两个数是不参与比较的。
  6. 依次类推,每一趟比较次数减少依次

【算法篇C++实现】常见排序算法,数据结构与算法,算法,排序算法,c++

时间复杂度:

  • N个数字要排序完成,总共进行N-1趟排序
  • 每i趟的排序次数为(N-i)次,所以可以用双重循环语句,外层控制循环多少趟,内层控制每一趟的循环次数
  • 冒泡排序的优点:每进行一趟排序,就会少比较一次,因为每进行一趟排序都会找出一个较大值。如上例:第一趟比较之后,排在最后的一个数一定是最大的一个数,第二趟排序的时候,只需要比较除了最后一个数以外的其他的数,同样也能找出一个最大的数排在参与第二趟比较的数后面,第三趟比较的时候,只需要比较除了最后两个数以外的其他的数,以此类推……也就是说,没进行一趟比较,每一趟少比较一次,一定程度上减少了算法的量。
  • 如果我们的数据正序,总共只需要走一趟,这一趟比较N-1次,时间复杂度为O(N)
  • 最坏情况我们的数据是反序的,则需要进行n-1趟排序。每趟排序要进行n-i次比较,总共进行n(n-1)/2次比较。时间复杂度为O(N^2)

C语言代码实现:

#include <stdio.h>
 
void BubbleSort(int arr[],int len)
{
	if (len < 1 || arr==nullptr) return;
 
	for(int i=0;i<len;i++)
		for (int j=0; j < len-i-1; j++)
		{
			if (arr[j]> arr[j + 1])
			{
				int temp = arr[j + 1];
				arr[j + 1] = arr[j];
				arr[j] = temp;
			}
		}
}
 
void PrintAddr(int arr[], int len)
{
	for (int i = 0; i < len; i++)
		printf("%d ", arr[i]);
	printf("\n");
}
 
int main()
{
	int arr[] = { 10,1,35,61,89,36,55};
	int len = sizeof(arr) / sizeof(arr[0]);
	BubbleSort(arr, len);
	PrintAddr(arr, len);
}

🚀三、插入排序

**算法精炼:**通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用 in-place 排序(即只需用到 O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

具体描述:

  1. 从第一个元素开始,该元素可以认为已经被排序;
  2. 取出下一个元素,在已经排序的元素序列中从后向前扫描;
  3. 将该元素从后往前与每一个已排序元素比较,找到恰好的位置插入,大于前一个,小于后一个
  4. 将新元素插入到该位置;重复以上步骤 。

例子:

【算法篇C++实现】常见排序算法,数据结构与算法,算法,排序算法,c++

C语言代码实现:

#include <stdio.h>
 
void InsertSort(int arr[], int len)
{
	for (int i = 1; i < len; i++)
	{
		int curVaule = arr[i]; //从第二个元素开始
		int preIndex = i - 1;  //第一个元素下标
		
		while (preIndex >= 0 && arr[preIndex] > curVaule) //第一个数比新元素大
		{
			arr[preIndex + 1] = arr[preIndex];  //大的往后移
			preIndex--;  //继续判断前一个数
		}
		arr[preIndex + 1] = curVaule;  //直到找到小于或者等于新元素的数,while循环里面减去了1判断前一个,所以要加上
	}
}
 
void PrintAddr(int arr[], int len)
{
	for (int i = 0; i < len; i++)
		printf("%d ", arr[i]);
	printf("\n");
}
int main()
{
	int arr[] = { 171,161,163,165,167,169 };
	int len = sizeof(arr) / sizeof(arr[0]);
	InsertSort(arr, len);
	PrintAddr(arr, len);
}

🚀四、希尔排序

插入排序虽好,但是某些特殊情况也有很多缺点,比如像下面这种情况

【算法篇C++实现】常见排序算法,数据结构与算法,算法,排序算法,c++

169 前的元素基本不用插入操作就已经有序, 元素 1 和 2 的排序几乎要移动数组前面的所有元素!!! 于是,有个老帅哥就提出了优化此问题的希尔排序!

算法精炼:是希尔(Donald Shell)于 1959 年提出的一种排序算法。也是一种插入排序,它是简单插入排序经过改进之后的一个更高效的版本,也称为缩小增量排序。它与插入排序的不同之处在于,它会优先比较距离较远的元素 。

基本步骤:

  1. 选择增量 : gap=length/2,缩小增量: gap = gap/2
  2. 增量序列:用序列表示增量选择, {n/2, (n/2)/2, …, 1}
  3. 先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,具体算法描述:
    • 选择一个增量序列 t1,t2,…,tk,其中 ti>tj,tk=1;
    • 按增量序列个数 k,对序列进行 k 趟排序;
    • 每趟排序,根据对应的增量 ti,将待排序列分割成若干长度为 m 的子序列,分别对各子表进行直接插入排序;
    • 仅增量因子为 1 时,整个序列作为一个表来处理,表长度即为整个序列的长度。

【算法篇C++实现】常见排序算法,数据结构与算法,算法,排序算法,c++

C语言代码实现

#include<stdio.h>
void ShellSort(int arr[], int len)
{
	
	for (int gap = len / 2; gap > 0; gap /= 2)
	{
		for (int i = gap; i<len; i++) //每个组执行插入排序
		{
			int curValue = arr[i]; //arr[i]就是第一组的第二个数据
			int preIndex = i - gap; //自然这个就是第一组的第一个元素
 
			while (preIndex >= 0 && arr[preIndex] > curValue)
			{
				arr[preIndex + gap] = arr[preIndex];
				preIndex -= gap;
			}
			arr[preIndex + gap] = curValue;
		}
	}
}
void PrintAddr(int arr[], int len)
{
	for (int i = 0; i < len; i++)
		printf("%d ", arr[i]);
	printf("\n");
}
int main()
{
	int arr[] = { 8,9,1,7,2,3,5,4,6,0 };
	int len = sizeof(arr) / sizeof(arr[0]);
	ShellSort(arr, len);
	PrintAddr(arr, len);
}

🚀五、堆排序

**算法精炼:**指利用堆这种数据结构所设计的一种排序算法,它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素

基本步骤:

  1. 第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置
  2. 然后再从剩余的未排序元素中寻找到最小(大)元素,然后放到已排序的序列的末尾
  3. 以此类推,直到全部待排序的数据元素的个数为零

【算法篇C++实现】常见排序算法,数据结构与算法,算法,排序算法,c++

C语言代码实现

void heapSort(Heap &heap){
    if (heap.size<1) return ;
    
    while(heap.size>0){
        int tmp = heap.arr[0];
        heap.arr[0] = heap.arr[heap.size-1];
        heap.arr[heap.size-1] = tmp;
        
        heap.size--;
        adjustDown(heap, 0);// 向下执行堆调整
    }
}

其中要用到堆的向下调整算法,因为当我们将数组进行一次选择排序后,就不满足最大堆了。所以找到堆最大元素比较麻烦,但调整到最大堆后,就很方便找到为heap.arr[0]

堆相关的知识:【数据结构篇C++实现】- 树

堆的向下调整算法:

/*向下调整将当前的节点和子节点调整成最大堆*/
void adjustDown(Heap &heap, int index) { 
    int cur=heap.arr[index];//当前待调整的节点
	int parent,child;
/*判断否存在大于当前节点子节点,如果不存在 ,则堆本身是平衡的,不需要调整;如果存在,则将最大的子节点与之交换,交换后,如果这个子节点还有子节点,则要继续按照同样的步骤对这个子节点进行调整*/
	for(parent=index; (parent*2+1)<heap.size; parent=child) {
        child=parent*2+1;
        
        //取两个子节点中的最大的节点
        
        if(((child+1)<heap.size)&&(heap.arr[child]<heap.arr[child+1])) {
        	child++;
		}
        
            //判断最大的节点是否大于当前的父节点
         if(cur>=heap.arr[child]) {//不大于,则不需要调整,跳出循环
             break;
         }else {//大于当前的父节点,进行交换,然后从子节点位置继续向下调整
             heap.arr[parent]=heap.arr[child];
             heap.arr[child]=cur;
         }
    }
}

🚀六、归并排序

算法精炼:归并排序是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分为(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起,即分而治之)

分治法:【算法篇C++实现】五大常规算法

【算法篇C++实现】常见排序算法,数据结构与算法,算法,排序算法,c++

可以看到这种结构很像一棵完全二叉树,本文的归并排序我们采用递归去实现(也可采用迭代的方式去实现):

  1. 阶段:可以理解为就是递归拆分子序列的过程,递归深度为log2n。
  2. 阶段:**即合并相邻有序子序列:**我们需要将两个已经有序的子序列合并成一个有序序列,比如上图中的最后一次合并,要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列,合并为最终序列[1,2,3,4,5,6,7,8],来看下实现步骤。

【算法篇C++实现】常见排序算法,数据结构与算法,算法,排序算法,c++

【算法篇C++实现】常见排序算法,数据结构与算法,算法,排序算法,c++

C语言代码实现:

#include <stdio.h>
#include<string.h>
void MergeAdd(int arr[], int left, int mid, int right, int *temp)
{
	int lmin = left; //指向左边数组最小元素位置
	int rmin = mid;  //指向右边数组最小元素位置(实参是mid+1)
	int index = left; //临时数组下标
	
	while (lmin<mid && rmin<=right)
	{
		if (arr[lmin] < arr[rmin])
		{
			temp[index++] = arr[lmin++];	
		}
		else
		{
			temp[index++] = arr[rmin++];
		}
	}
 
    //如果是右边数组先移完
	while (lmin < mid)
		temp[index++] = arr[lmin++];
 
    //如果是左边数组先移完
	while (rmin <= right)
		temp[index++] = arr[rmin++];
 
	memcpy(arr + left, temp + left, sizeof(int)*(right - left + 1));
}
 
void MergeSort(int arr[], int left, int right, int *temp)
{
	if (left <0 || arr == nullptr) return;
 
	if (left < right)
	{
		int mid = (right+left)/2;
		MergeSort(arr, left, mid, temp);  	//左边一半递归实现
		MergeSort(arr, mid+1, right, temp); //右边一半递归实现
		MergeAdd(arr, left, mid + 1, right, temp); 	//分到最后,合并子列项
	}
}

void PrintAddr(int arr[], int len)
{
	for (int i = 0; i < len; i++)
		printf("%d ", arr[i]);
	printf("\n");
}
int main()
{
		int arr[] = { 8,9,1,7,2,3,5,4,6,0 };
		int len = sizeof(arr) / sizeof(arr[0]);
 
		int *temp = new int[len];
		MergeSort(arr,0,len-1,temp);
		PrintAddr(arr, len);
		delete temp;
}

🚀七、快速排序

**算法精炼:**每次选取第一个数为基准数;然后将大于和小于基准的元素分别放置于基准数两边–>“乾坤大挪移”;继续分别对基准数两侧未排序的数据使用分治法进行细分处理,直至整个序列有序。

【算法篇C++实现】常见排序算法,数据结构与算法,算法,排序算法,c++

【算法篇C++实现】常见排序算法,数据结构与算法,算法,排序算法,c++

C语言代码实现:

#include <stdio.h>
int partition(int arr[], int low, int high)
{
	int i = low;
	int j = high;
	int base = arr[low]; //选择第一个数作为基准
 
	if (low < high)
	{
		while (i < j)
		{
			while (i < j && arr[j] >= base) 
			{
				j--; //从右往左找到比基准数小的
			}
			if (i < j)//右边有比基数小的数(排除j<i的情况)
			{
				arr[i++] = arr[j];
			}
 
			while (i < j&&arr[i] < base) 
			{
				i++; //从左往右找到比基准数大的
			}
			if (i < j)//左边有比基数大的数
			{
				arr[j--] = arr[i];
			}
		}
 
		arr[i] = base;
	}
	return i;
}
//快速排序
void QuickSort(int arr[], int low, int high)
{
	if (low < high)
	{
		int index = partition(arr, low, high); //快速排序
		QuickSort(arr, low, index - 1); //左边一半快速排序
		QuickSort(arr, index + 1, high); //右边一半快速排序
	}
}
 
void PrintAddr(int arr[], int len)
{
	for (int i = 0; i < len; i++)
		printf("%d ", arr[i]);
	printf("\n");
}
int main()
{
	int arr[] = { 163, 161, 158, 165, 171, 170, 163, 159, 162 };
 
	int len = sizeof(arr) / sizeof(arr[0]);
	QuickSort(arr, 0, len - 1);
	PrintAddr(arr, len);
}

⛳总结:

排序算法 平均时间复杂度 最好情况 最坏情况 排序方式 稳定性
冒泡排序 O(n * n) O(n) O(n * n) In-place 稳定
选择排序 O(n * n) O(n * n) O(n * n) In-place 不稳定
插入排序 O(n * n) O(n) O(n * n) In-place 稳定
希尔排序 O(n * log n) O(n * log n) O(n * log n) In-place 不稳定
归并排序 O(n * log n) O(n * log n) O(n * log n) Out-place 稳定
堆排序 O(n * log n) O(n * log n) O(n * log n) In-place 不稳定
快速排序 O(n * log n) O(n * log n) O(n * n) In-place 不稳定

到了这里,关于【算法篇C++实现】常见排序算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】常见的排序算法

    常见的七大排序算法: 最好的情况是O(n),数组为升序 最坏的情况是O(n 2 ),数组为降序 元素集合越接近有序,直接插入排序算法的时间效率越高 时间复杂度:O(N^2) 空间复杂度:O(1),它是一种稳定的排序算法 稳定性:稳定 针对直接插入排序中,当数组属于降序时,时间复杂

    2024年02月14日
    浏览(39)
  • 【数据结构】 常见的八大排序算法

    排序有 内部排序和外部排序 ,内部排序是数据记录在内存中进行排序,这里八大排序就是内部排序,指直接插入,希尔,选择,堆排,冒泡,快排,归并,计数。 下面让我们来共同学习这八大排序吧!🤗🤗🤗 什么是外部排序: 外排序是数据量较大,内存放不下,数据放到外

    2024年02月12日
    浏览(112)
  • 【数据结构】常见排序算法——常见排序介绍、选择排序(直接选择排序、堆排序)交换排序(冒泡排序)

      选择排序是一种简单但不高效的排序算法,其基本思想是从待排序的数据中选择最小(或最大)的元素放到已排序的数据末尾。具体操作步骤如下: (1)找到数据中最小的元素,并把它交换到第一个位置; (2)在剩下未排序的元素中找到最小的元素,并把它交换到已排

    2024年02月04日
    浏览(56)
  • 【数据结构】——常见排序算法(演示图+代码+算法分析)

    目录 1.  常见排序算法 1.2 稳定性 2.  常见排序算法的实现 2.1 插入排序 2.1.1基本思想 2.1.2代码 2.1.4算法分析  2.2 希尔排序 2.2.1基本思想 2.2.2代码 2.2.3演示图  2.2.4算法分析 2.3 选择排序 2.3.1基本思想 2.3.2代码 2.3.3演示图 2.3.4算法分析 2.4 堆排序 2.4.1基本思想  2.4.2代码 2.4.3演示

    2024年02月11日
    浏览(73)
  • 【数据结构---排序】庖丁解牛式剖析常见的排序算法

    排序在我们生活中处处可见,所谓排序,就是使一串记录,按照其中的某个或某些的大小,递增或递减的排列起来的操作。 常见的排序算法可以分为四大类:插入排序,选择排序,交换排序,归并排序;其中,插入排序分为直接插入排序和希尔排序;选择排序分为直接

    2024年02月16日
    浏览(62)
  • 【一起学数据结构与算法】几种常见的排序(插入排序、选择排序、交换排序、归并排序)

    排序是计算机内经常进行的一种操作,其目的是将一组 “无序” 的记录序列调整为 “有序” 的记录序列。分 内部排序 和 外部排序 ,若整个排序过程不需要访问外存便能完成,则称此类排序问题为内部排序。反之,若参加排序的记录数量很大,整个序列的排序过程不可能

    2023年04月09日
    浏览(46)
  • 【C++】数据结构与算法:常用排序算法

    😏 ★,° :.☆( ̄▽ ̄)/$: .°★ 😏 这篇文章主要介绍常用排序算法。 学其所用,用其所学。——梁启超 欢迎来到我的博客,一起学习,共同进步。 喜欢的朋友可以关注一下,下次更新不迷路🥞 排序算法是计算机科学中常见的一类算法,用于将一组数据按照特定的顺序进行排

    2024年02月14日
    浏览(49)
  • C++基础-介绍·数据结构·排序·算法

    C++是一门风格严谨又不失自由的开发语言,提供了完整的内存管理、支持函数式编程和面向对象编程,支持模板、多继承、多实现、重载、重写等多态特性。 优势在于目前90%的操作系统、数据库、应用基础架构、硬件嵌入式等都是使用C/C++制作的,而C++是对C的标准扩展,掌握

    2024年02月03日
    浏览(45)
  • 常见排序集锦-C语言实现数据结构

    目录 排序的概念 常见排序集锦      1.直接插入排序      2.希尔排序      3.选择排序      4.堆排序      5.冒泡排序      6.快速排序             hoare              挖坑法             前后指针法             非递归      7.归并排序             非递归 排序实现

    2024年02月12日
    浏览(49)
  • 数据结构——C语言实现常见排序(插入排序、希尔排序、选择排序、堆排序、冒泡排序)

    现在是北京时间2023年6月23日13点19分,度过了一个非常愉快的端午节。由于刚从学校回家,一下子伙食强度直升了个两三个档次。这也导致我的肠胃不堪重负,我也准备等会去健身房消耗一下盈余的热量。回到家陪伴爷爷走人生最后的阶段才是我这个暑假最重要的事情。自从

    2024年02月10日
    浏览(53)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包