网站建设电话咨询,元氏县城有做网站广告的吗,电影爱好网,wordpress 视差主题目录
快速排序
直接插入排序
改良版冒泡排序 快速排序
理解#xff1a; ①从待排序元素中选定一个基准元素#xff1b; ②以基准元素将数据分为两部分#xff1a;#xff08;可以将#xff1a;大于基准元素放左#xff0c;小于基准元素放右#xff09; ③对左半部分…目录
快速排序
直接插入排序
改良版冒泡排序 快速排序
理解 ①从待排序元素中选定一个基准元素 ②以基准元素将数据分为两部分可以将大于基准元素放左小于基准元素放右 ③对左半部分从左端到基准数据进行①②操作直到数据有序 即将左端到基准数据作为范围传入这个范围又会产生新的范围左端到基准数据2 …… 直到数据有序 ④对左半部分从基准数据到右端进行①②操作 【粗劣分析便于理解】 右半部分 【深层分析便于代码】 遍历直倒有序 数据有序后返回上一层 代码思路 /* 思路 选定一个基准(默认左端): 用变量temp记录基准值; loop: 此时左端所在下标low代表的值可以被覆盖(值已经被复制了) 从右端向左端的方向,开始与temp比较,直到遇到比temp小的数,(否则就high--左移),将这个小于temp的数(下标可假定为high)放到左边左边下标low所在的数据上 此时右端所在下标high代表的值可以被覆盖(值已经复制到下标low代表的值内了) 从左端向左端的方向,开始与temp比较,直到遇到比temp大的数,(否则就low后移),将这个大于temp的数(下标可假定为low)放到右边左边下标high所在的数据上 此时左端low下标的数据可以被覆盖回到loop; 循环结束条件:low后移high前移 直到相遇说明以基准值temp将这批数据分成两份完毕。 注意此时大小两份虽然分类完成但是 作为基准值的数据 还未找到位置【基准值应该放在下标为low的位置】 看下面图理解 注意此时应lowhigh并且理应必须lowhigh 注意此时下标所在位置的数据应该被覆盖 故基准值应该放在下标为low的位置(或者下标为high反正两值相等) ********************************************************* 《基准值临界情形图》 基准值5 x x x x 6 3 x x x l h 此时基准值正在与l所代表元素比较l向右移中说明h位置是无用数据 x x x x 6 6 x x x l h l数据复制给h,轮到下标h向左移动 x x x x 6 6 x x x ↑ 两下标重合相等此时应该放入基准值temp(h现在是无用数据)(low左边比基准值小high右边比基准值大) 基准值7 x x x x 6 5 x x l h 此时基准值正在与l所代表元素比较h向左移动中说明l位置是无用数据 x x x x 5 5 x x l h h数据复制给l,轮到下标l向左移动(h现在是无用数据) x x x x 5 5 x x ↑ 两下标重合相等此时应该放入基准值temp(h现在是无用数据)(low左边比基准值小high右边比基准值大) ********************************************************* */ 全部代码
#include stdio.h//显示函数
void showData(int buf[],int len)
{//显示for(int i0;ilen;i)printf(%d ,buf[i]);printf(\n);
}//快速排序函数/*************************************************************************
函数功能: 对传入的数据进行一次快速排序分成大于基准值和小于基准值的两部分
输入参数: 待排序的数组需要排序的下标范围左端下标、右端下标;
返回值 基准所在的下标
*************************************************************************/
/*
思路
选定一个基准(默认左端): 用变量temp记录基准值;loop:
此时左端所在下标low代表的值可以被覆盖(值已经被复制了)
从右端向左端的方向,开始与temp比较,直到遇到比temp小的数,(否则就high--左移),将这个小于temp的数(下标可假定为high)放到左边左边下标low所在的数据上此时右端所在下标high代表的值可以被覆盖(值已经复制到下标low代表的值内了)
从左端向左端的方向,开始与temp比较,直到遇到比temp大的数,(否则就low后移),将这个大于temp的数(下标可假定为low)放到右边左边下标high所在的数据上此时左端low下标的数据可以被覆盖回到loop;循环结束条件:low后移high前移 直到相遇说明以基准值temp将这批数据分成两份完毕。注意此时大小两份虽然分类完成但是 作为基准值的数据 还未找到位置【基准值应该放在下标为low的位置】看下面图理解
注意此时应lowhigh并且理应必须lowhigh
注意此时下标所在位置的数据应该被覆盖
故基准值应该放在下标为low的位置(或者下标为high反正两值相等)
*********************************************************
《基准值临界情形图》
基准值5
x x x x 6 3 x x xl h 此时基准值正在与l所代表元素比较l向右移中说明h位置是无用数据
x x x x 6 6 x x xl h l数据复制给h,轮到下标h向左移动
x x x x 6 6 x x x↑ 两下标重合相等此时应该放入基准值temp(h现在是无用数据)(low左边比基准值小high右边比基准值大)
基准值7
x x x x 6 5 x x l h 此时基准值正在与l所代表元素比较h向左移动中说明l位置是无用数据
x x x x 5 5 x xl h h数据复制给l,轮到下标l向左移动(h现在是无用数据)
x x x x 5 5 x x↑ 两下标重合相等此时应该放入基准值temp(h现在是无用数据)(low左边比基准值小high右边比基准值大)
*********************************************************
*/int part(int arr[],int low,int high)
{//检查输入范围是否合法if(lowhigh){return -1;}//选定一个基准值(以左端作为基准值)int temparr[low];//注意:下标low所在数据被temp保存//结束循环的条件while(lowhigh){//比较右端,比基准大的仍然放在右边不用管继续向前判断下一个:故high--;while(temparr[high]lowhigh){high--;//下标向前移动判断下一个}//条件不满足时出循环将这个小数据放到左边下标为low的地方(low数据已经被保存)arr[low]arr[high];//开始比较左端:比基准小得仍然放左边继续向后判断下一个while(temparr[low]lowhigh){low;}//条件不满足跳出循环将这个小数据放到左边arr[high]arr[low];//此时high所在数据之前已经被放到循环前的low里了/*注意:这里内层循环增设了条件为lowhigh,图形解释: 见最下方《基准值临界情形图》PRO文字解释:当low与high相差为1时假定low与low将值给high开始判断high,此时high的值必定会满足所以high会左移high移动到low的位置仍然会满足值的条件条件high继续移动到low的左边此时high值不满足条件出循环并且交换数据回到大循环判断lowhigh*/}//运行到此说明lowhigh;arr[high]temp;return high;//基准所在下标low或者high都可以
}void quick_sort(int arr[],int low,int high)
{if(lowhigh){return;}int midpart(arr,low,high);quick_sort(arr,low,mid-1);quick_sort(arr,mid1,high);
}int main()
{int arr[]{82,15,49,85,28,43,39,17,47,48};int lensizeof(arr)/sizeof(arr[0]);printf(len%d\n,len);//快速排序quick_sort(arr,0,9);//数据显示showData(arr,len);
}/*
*********************************************************
《基准值临界情形图》PRO 临界情形分析
基准值5
x x x x 6 3 x x xl h 此时基准值正在与l所代表元素比较l向右移中说明h位置是无用数据
x x x x 6 6 x x xl h l数据复制给h,轮到下标h向左移动
x x x x 6 6 x x x↑ 两下标重合相等此时应该放入基准值temp(h现在是无用数据)
x x x x 6 6 x x xh l 内层循环不加lowhigh;则h会一直移动直到小于基准值才回到外层循环判断lowhigh
基准值7
x x x x 6 5 x x l h 此时基准值正在与l所代表元素比较h向左移动中说明l位置是无用数据
x x x x 5 5 x xl h h数据复制给l,轮到下标l向左移动(h现在是无用数据)
x x x x 5 5 x x↑ 两下标重合相等此时应该放入基准值temp(h现在是无用数据)
x x x x 5 5 x xh l 内层循环不加lowhigh;则l会一直移动直到大于基准值才回到外层循环判断lowhigh
*********************************************************
*/
直接插入排序
//直接插入排序
void insert_sort(int arr[],int len)
{for(int i1;ilen;i)//{int temparr[i];//选定第i个进行插入int j;for(ji-1;j0arr[j]temp;j--)//将在我之前的数据依次向后搬运直到遇到第一个比自己小的元素{arr[j1]arr[j];}arr[j1]temp;//插入位置注意执行了j--才出的循环}
}
改良版冒泡排序
//改良版冒泡排序
void bubble_sort(int buf[],int len)
{int temp;int flag1;for(int i0;ilenflag;i)//轮数{flag0;//使用标志位前标志位初始值for(int j0;jlen-1-i;j)//每轮比较次数{if(buf[j]buf[j1]){flag1;//发生交换标志位置1tempbuf[j1];buf[j1]buf[j];buf[j]temp;}}//一轮下来没有发生交换排序已完成跳出循环}
}
