wordpress 网站描述,百度首页官网,网站前台代码,wordpress 媒体库清理引言
快速排序一直是排序算法中使用比较高频的一种算法。下面简述一下快排#xff0c;予以记录。
实现思想
在一组无序的数组中#xff0c;定义一个标志flag#xff0c;这里以数组中左起第一个元素作为标志#xff0c;定义一个i值和j值#xff0c;分别表示从左边开始与…引言
快速排序一直是排序算法中使用比较高频的一种算法。下面简述一下快排予以记录。
实现思想
在一组无序的数组中定义一个标志flag这里以数组中左起第一个元素作为标志定义一个i值和j值分别表示从左边开始与flag比较的数组元素下标从右边开始与flag比较的数组元素下标这里需要注意的是若选择数组中左起第一个元素为flag,则先从右开始与flag比较反之亦然。当下标j 和下标i的元素相同的情况下停止此次排序用flag与当前下标i(下标i和下标j相等)的元素进行交换就能满足左边小于flag的值右边大于flag的值。然后以左边的元素构成一个数组依旧选择左起第一个元素为flag,同时下标i为左起第一个元素的下标下标j为数组的右侧最后一个元素的下标开始比较排序类似之前的操作。下面举例说明。 23546345512467829 上面的数组中选择左起第一个元素 23作为flag,定义i和j作为下标分别指向最左边和最右边即i指向23j指向29现在进行第一轮排序要求左边的元素小于等于23右边的元素大于等于23。29大于23满足要求j–,此时j指向元素8823不满足右边的元素大于flag,停止右边的移动比较开始比较左边i下标的元素23等于23满足条件开始下一位545423,不满足条件这时交换54与8的值交换后数组元素的值为 23863455124675429 接下来进行第二次排序。此时经过上一次的排序后下标i处的元素是8下标j处的元素为54,接着j–,j处的元素为676723满足条件j–,下标j处的元素为4423不满足条件停止右侧的比较开始左侧的比较左侧下标i处的元素为8满足条件i下标i处的元素为6623满足条件i,下标i处的元素为343423不满足条件交换下标i处是元素34与下标j处的元素4交换后数组的元素为 23864551234675429 接着比较右边j下标处的元素3423满足条件j–,下标j处的元素为121223不满足条件左边下标i处的元素为4423满足条件i,下标i处的元素为555523不满足条件交换下标i处的元素55与下标j处的元素12交换后数组的元素为 23864125534675429 接着比较右侧下标j处的元素555523满足条件j–,下标j处的元素为121223不满足条件停止右侧下标j的元素比较此时左侧的元素下标i 和右侧的元素下标j都为同一个元素的下标这时用flag与下标为i的元素进行交换交换后元素的值为 12864235534675429 这样完成了第一轮排序实现了23左侧比23小右侧比23大。下面以23左侧的元素构成一个数组 ”12864“ 依旧选取12为flag,下标i处的元素为12下标j处的元素为4从右侧开始比较412,不满足条件停止下标j处的元素比较开始下标i处的元素比较1212满足条件i,下标i处的元素为88 12满足条件i,下标i处的元素为66!2满足条件i下标i处的元素为4此时下标i处的元素和下标j处的元素是同一个元素停止下标i的比较用flag与下标i处的元素4交换位置交换后的数组 ”48612“ 此时12以左的元素小于12这时以12以左的元素构成一个数组 ”486“ 左起第一个元素4为flag,下标i处的元素为4下标j处的元素为6开始右侧的元素比较6 4满足条件j–,下标j处的元素为884满足条件j–下标j处的元素为4此时下标i处的元素和下标j处的元素相等交换flag与下标i处的元素flag和下标i处的元素为同一个元素此时4右侧的元素比4大以右侧的元素组成一个数组 ”86“ 同理flag为8下标i处的元素为8下标j处的元素为6开始右侧的比较68不满足条件开始左侧的比较下标i处的元素为888满足条件i下标i处的元素为6此时下标i和下标j为同一个元素的下标交换flag和下标i的元素交换后数组 “6,8” 8左侧比8小此时在最开始以第一个元素23为标志得到的左侧的数组为 ”46812“ 23右侧的数组 ”5534675429* 同理以第一个元素55为flag,下标i处的元素为55下标j处的元素为29开始右侧的比较2955不满足条件开始左侧的比较,下标i处的元素5555等于55i下标i处的元素为343455满足条件i,下标i处的元素为676755不满足条件交换下标i和下标j处的元素得到数组 “5534295467” 此时下标j处的元素为6767 55,满足条件j–下标j处的元素为545455不满足条件下标i处的元素为292955满足条件i下标i处的坐标为54下标i和下标j处的元素为同一个元素交换flag与下标i处的元素得到数组 “5434295567” 这时55右侧比55大左侧元素比55小以左侧元素构成数组 “543429” 第一个元素54为flag,下标i为54的下标下标j为数组的右侧最后一个元素的下标开始右侧的比较下标j处的元素2954不满足条件下标i处的元素54等于54i下标i处的元素为343454满足条件i,下标i处的元素为29下标i处的元素与下标j处的元素为同一个元素交换小标i处的元素与flag得到 “293454” 54左侧的元素比54小以54左侧的元素构成一个数组得到 “2934” 同样flag为第一个元素下标i为29的下标下标j为右侧最后一个元素34的下标开始比较右侧3429满足条件j–,下标j处的元素为29此时下标i和下标j处的元素为同一个元素交换flag与下标i处的元素排序后 “2934” 此时55左侧的元素顺序为 “293454” 55右侧只有一个元素67整个数组的排序已经排完完整的顺序为 “46812232934545567” 整个实现的比较就是上面所说。
实现
#include QCoreApplication
#include stdio.h#if 0
void my_print(char text[])
{printf(my_print()%d\n,sizeof(text));
}
int main(int argc, char *argv[])
{QCoreApplication a(argc, argv);char test[]Welcome to China;my_print(test);printf(main()%d,sizeof(test));return 0;
}
#endif#if 0
#include QVector
#include QString
#include QDebug
using namespace std;struct Grade
{string name;int grade;
};int main()
{Grade subject[3] {{ English, 80 },{ Biology, 70 },{ History, 90 }};int sum accumulate(subject, subject 3, 0, [](int a, Grade b){return a b.grade; });string strObject accumulate(subject,subject3,string( ),[](string str1,Grade str2){return str1str2.name;});//accumulate如果是字符串求和第三个参数必须是string( )qDebug() sumstrObjectstrObject.data()/*.c_str()*/;//240system(pause);return 0;
}
#endif#include iostream
using namespace std;void outputArr(int *arr,int count){for (int i 0; i count; i) {coutarr[i] ;}
}//快速排序
void quickSort(int *arr,int left,int right){//left-下标起始值小标结束值if (left right) {return ;}int flag arr[left];int i left;int j right;int temp;while (i j) {while (i j arr[j] flag) {//不能排除相等的情况否则不适用于含有重复元素--j;}while (i j arr[i] flag) {i;}if (i j) {temp arr[i];arr[i] arr[j];arr[j] temp;}}if (arr[i] arr[j]) {//一轮比较结束后i和j相等temp arr[i];arr[i] arr[left];arr[left] temp;}quickSort(arr,left,i-1);quickSort(arr,i1,right);
}int main()
{int nums[] {23,1,34,4,6,78,33,9,5};quickSort(nums,0,6);//传入下标的范围outputArr(nums,9);coutendl;coutendl;int nums1[] {7,1,34,4,6,8,33,9,43,6};quickSort(nums1,0,9);outputArr(nums1,10);coutendl;return 0;
}以上便是实现。
