排序算法整理

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

排序算法整理,算法,排序算法,算法,c++文章来源地址https://www.toymoban.com/news/detail-800665.html

快速排序

C实现

void fastStore(int *a, int start, int end){
    
	if(start>=end)
		return ;
	
	int left=start;
	int right=end;
	int temp=a[left];//设置基准值temp
	
	while(left < right)		//左指针的位置一定小于右指针的位置
	{
		while(a[right]>temp && left < right)	
							//左指针要在右指针的左面
		{
			right--;
		}
		a[left] = a[right];
		left++;
		
		while(a[left] < temp && left < right){
			left++;
		}
		a[right] = a[left];
		right--;
		a[left] = temp;
	}
  
    fastSort(a,start,left-1);
    fastSort(a,right+1,end);
} 
void FastSort(int *a,int start,int end)
{
	if(start>=end)//递归条件
	{
		return; //跳出递归
	}
	//初始化左右指针
	int left = start;
	int right = end;
	int temp = a[left]; 			//基准值
	while(left < right)
	{
		while(a[right]>temp && left < right)
		{
			right--;
		}
		a[left] = a[right];	//将右指针的值赋给左指针
		left++;
		while(a[left]<temp && left<right)
		{
			left++;
		}
		a[right] = a[left];
        right--;
        a[left] = temp;	//把基准值赋给左指针
        
	}
	FastSort(a,start, left-1);	//左面
	FastSort(a,right+1, end);	//右面
}

C++实现

#include<iostream>
 
//快排具体实现
template<typename T>
void showNum(T *num,int len)
{
    for (int j = 0; j < len; j++)
    {
        std::cout<<num[j]<<" ";
    }
    std::cout<<std::endl;
}
template<typename T>
int part(T* arr, int left, int right)  //划分函数
{
    int i = left; 
    int j = right;
    T fidValue = arr[left];
    while (i < j)
	{
		while (i<j && arr[j]>fidValue) //从右向左开始找一个 小于等于 pivot的数值
		{
			j--;
		}
		if (i < j)
		{
			std::swap(arr[i++], arr[j]);  //r[i]和r[j]交换后 i 向右移动一位
		}
		while (i < j && arr[i] <= fidValue) //从左向右开始找一个 大于 pivot的数值
		{
			i++;
		}
		if (i < j)
		{
			std::swap(arr[i], arr[j--]);  //r[i]和r[j]交换后 i 向左移动一位
		}
	}
	return i;  //返回最终划分完成后基准元素所在的位置
}

template<typename T>
void fastSort(T *arr,int left,int right)
{
    int mid;
	if (left < right)
	{
		mid = part(arr, left, right);  // 返回基准元素位置
		fastSort(arr, left, mid - 1); // 左区间递归快速排序
		fastSort(arr, mid+1, right); // 右区间递归快速排序
	}
}
template<typename T>
void Sort(T *num,int len)
{
    fastSort(num,0,len-1);
}

int main()
{
    int num[] = {4,2,1,6,3,8,12,0,34};
    Sort<int>(num,sizeof(num)/sizeof(num[0]));
    showNum<int>(num,sizeof(num)/sizeof(num[0]));

    std::string str[]={"w ","c ","d ","a "};
	Sort<std::string>(str,sizeof(str)/sizeof(str[0]));
	showNum<std::string>(str,sizeof(str)/sizeof(str[0]));

    return 0;
}

插入排序

#include<stdio.h>

//显示数组
void ShowArray(int *num, int size)
{
    for (int i = 0; i < size; i++)
    {
        printf("%d ",num[i]);
    }
    printf("\n");
}
//插入排序: 与冒泡相反,在开始遍历数据时,就进行数据的排序,遍历后的数据实现有序
/***
 * 具体实现:
 * 对数据进行遍历,对遍历到某位置的数据,
 * 通过临时值,实现与该位置之前的所有数据的比较,   
 * (因为在循环中,所以,该位置之前的所有数据是有序的)
 * 当 该值 大于前一位置的值时,即可,跳出比较循环,并将temp赋给当前位置j
*/
void InsertSort(int *num, int len)
{
    for(int i=0;i<len;i++)
    {
        int temp=num[i];    //一个临时值
        int j=i;
        for(;j>0;j--){
            if(temp<num[j-1]){  //和i位置之前的所有数据进行比较
                num[j]=num[j-1];	//把大值放在右面
            }
            else{   //temp>num[j-1], 即temp大于前一个数
                break;	//跳出第二层循环,并将当前的j位置的数值置为temp
            }
        }
        num[j]=temp;
    }  
}
 
int main()
{
    int num[]={2,7,1,4,8,3,9};
    InsertSort(num,sizeof(num)/sizeof(num[0])-1);
    ShowArray(num,sizeof(num)/sizeof(num[0]));
    return 0;
}

冒泡排序

#include<stdio.h>

//显示数组
void ShowArray(int *num, int size)
{
    for (int i = 0; i < size; i++)
    {
        printf("%d ",num[i]);
    }
    printf("\n");
}
//冒泡排序
/**
 * 算法思想:
 * 通过循环每次比较,将最大值放在最后
 * 这样,每次遍历循环的数据个数都会-1
 * 最后一个数据无需比较,默认最小值
*/
void BubbleSort(int *num,int size)
{
    //遍历,找寻最大值
    for (int i = 0; i < size-1; i++)    //最后一个数无需比较,自动上浮
    {   
        for (int j = 0; j <size-i-1; j++)   //size-i-1:是因为,前i个数据已经排成有序队列,无需再次比较: 
        {
            if (num[j]>num[j+1])    //每一轮比较的最大值都会上浮,即可排除该值,所以-i
            {
                int tmp = num[j];
                num[j]=num[j+1];
                num[j+1] = tmp;
            }
        }
    }
}

 
int main()
{
    int num[]={2,7,1,4,8,3,9};
    BubbleSort(num,sizeof(num)/sizeof(num[0]));
    ShowArray(num,sizeof(num)/sizeof(num[0]));
    return 0;
}

选择排序

#include<stdio.h>

//显示数组
void ShowArray(int *num, int size)
{
    for (int i = 0; i < size; i++)
    {
        printf("%d ",num[i]);
    }
    printf("\n");
}
//选择排序 : 
/**
 * 算法思想:
 * 选取左位置的数据为一最小值(或者最大值),与数据进行比较,找到最小值或最大值
 * 与当前的i位置的数据进行交换,保证遍历过的数据是有序的
*/
void ChooseSort(int *num, int len)
{
    int minnum = 0;
    for(int i=0;i<len;i++)
    {
        minnum = num[i];
        for (int j = i+1; j < len; j++)
        {
            if (num[j]<minnum)  //查找最小值,将当前位置的值与num[j]交换
            {
                int temp = minnum;  //选用下标,效率更高,将会减少了交换次数
                minnum = num[j];
                num[j] = temp;
            }
        }
        num[i]=minnum;        
    }  
}
void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
void ChooseSort2(int *num , int len)
{
    int i, j, minnum;
    for(i = 0; i < len; i++)
    {
        minnum = i; //下标
        for(j = i+1; j<len; j++)
        {
            if (num[j]<num[minnum]) //查找最小值的下标
                minnum = j;
        }
        swap(&num[minnum],&num[i]);
    }
}
 
int main()
{
    int num[]={2,7,1,4,8,3,9};
    ChooseSort2(num,sizeof(num)/sizeof(num[0])-1);
    ShowArray(num,sizeof(num)/sizeof(num[0]));
    return 0;
}

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

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

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

相关文章

  • 【排序算法】排序算法介绍及插入排序 ( 直接插入排序 && 希尔排序 )

    ​ ​📝个人主页:@Sherry的成长之路 🏠学习社区:Sherry的成长之路(个人社区) 📖专栏链接:数据结构 🎯 长路漫漫浩浩,万事皆有期待 排序 :所谓排序,就是将一串数据,按照某种规律,或者以某种特性或,将数据按照递增或者递减,将数据从 无序转变为有序

    2023年04月21日
    浏览(40)
  • 【算法】排序算法(插入排序、希尔排序、选择排序、冒泡排序、快速排序、归并排序、基数排序、堆排序)

    插入排序 :插入排序、希尔排序 选择排序 :选择排序、堆排序 交换排序 :冒泡排序、快速排序 归并排序 基数排序(又叫桶排序) (1)思路图解 从头开始比较相邻元素的值(就是从下标较小的元素开始),使值较大的元素逐渐从前移向后部,就像水里的气泡一样,越来越大,向上

    2024年03月25日
    浏览(51)
  • 【数据结构与算法】排序算法(选择排序,冒泡排序,插入排序,希尔排序)

    基本概念这了就不浪费时间解释了,这四种都是很简单的排序方式,本专栏后续文章会出归并排序,计数排序,快速排序,堆排序,桶排序等排序算法,今天这篇文章中给出选择排序,冒泡排序,插入排序和希尔排序的实现; 如果发现文章中有错误,还请大家指出来,我会非

    2024年02月15日
    浏览(81)
  • 【基础算法】八大排序算法:直接插入排序,希尔排序,选择排序,堆排序,冒泡排序,快速排序(快排),归并排序,计数排序

      🧑‍🎓 个人主页:简 料   🏆 所属专栏:C++   🏆 个人社区:越努力越幸运社区   🏆 简       介: 简料简料,简单有料~在校大学生一枚,专注C/C++/GO的干货分享,立志成为您的好帮手 ~ C/C++学习路线 (点击解锁) ❤️ C语言阶段(已结束) ❤️ 数据结构与算法(ing) ❤

    2024年02月01日
    浏览(45)
  • 【数据结构与算法】排序算法:冒泡排序,冒泡排序优化,选择排序、选择排序优化

    目录 一、冒泡排序 1、冒泡排序思想 2、冒泡排序算法的性能分析 代码实现: 二、选择排序 1、选择排序思想 2、选择排序算法的性能分析  代码实现: 1、冒泡排序思想 冒泡排序的基本思想是通过相邻元素之间的比较和交换来逐步将最大(或最小)的元素移到右边(或左边

    2024年01月19日
    浏览(49)
  • 算法专题整理:滑动窗口

    视频课程:同向双指针 滑动窗口【基础算法精讲 01】_哔哩哔哩_bilibili 滑动窗口也可以理解为双指针法的一种。 滑动窗口的核心在于 连续 !如果需要得到的结果是 满足某种较为明显条件 的 连续 的 子数组 ,可以考虑使用滑动窗口来做。 通常情况下,滑动窗口是 枚举右端

    2024年02月12日
    浏览(47)
  • 字符串常见算法整理

    句子反转 构造新字符串办法 字符串的旋转 移动数组 第 i(1)个出现N次的字符在当前字符串中的索引 第 i(1) 个不重复的字符在当前字符串中的索引 两个字符串比较求最优算法 比较差异度 拓扑结构相同的子树 变形词问题 子串判断 ## KMP算法实现 ## 处理字符环(加长一倍

    2024年02月16日
    浏览(49)
  • 算法整理六——动态规划

    基本思想是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。 动态规划算法的有效性依赖于问题本身所具有的两个重要性质: 最优子结构、重叠子问题 1、最优子结构:当问题的最优解包含了其子问题的最优解时,称该问题具有最优

    2024年02月03日
    浏览(26)
  • 搞懂PID算法(笔记整理)

    PID算法(比例-积分-微分法)是一种控制系统调节器,具有比例、积分和微分三部分组成,是一种常用的闭环控制算法。 PID算法的用途是在工业控制系统中,应用于控制过程、航空器TECS(Total Engine Control System)系统、火箭发射平台控制系统、轮式机器人的控制等方面,使用该

    2023年04月22日
    浏览(23)
  • 【排序算法】快速排序的基本算法

            快速排序是应用最广泛的排序算法,流行的原因是它实现简单,适用于各种不同的输入数据且在一般应用中比其他排序算法都要快得多。快速排序引人注目的特点是原地排序,只需要一个很小的辅助栈,且将长度为N的数组排序所需时间和NlgN成正比。另外,快速排序

    2024年01月22日
    浏览(50)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包