快速排序-笔记(防止题目重复)

野性酷女 2022-12-27 07:50 103阅读 0赞

快速排序  
冒泡排序

每次循环,相邻两元素两两比较,不符合则交换,最大元素沉底  
//随便写的,好像不对

void BmbleSort(SqList &L)
    {
        
    	for (int k = 1; k <= L.length - 1; k++)
    	{
        
    		for (int i = 1; i < L.length - k; i++)
    		{
        
    			if (L.r[i].key > L.r[i + 1].key)
    				swap(L.r[i], L.r[i + 1]);
    		}
    	}
    }

快速排序(Quick Sort)  
1 快速排序的原理  
递归边界:序列长为1或0则不必排序  
递归关系:  
薛烈长度大于1,则选择某元素作为枢轴(如最左侧元素)  
根据枢轴元素将原序列一份为二(划分)  
左右两侧子序列通过重复上述过程,递归完成各自的排序  
划分:选最左元素作为枢轴,备份之,令low和high指向两端  
先high向左找小元素移动到右侧,再low向右找元素移动到左侧,  
如此重复至两者相遇;  
填入枢轴,完成划分  
2 快速排序算法的实现

int Partition(SqList L, int low, int high)
    {
        
    	L.r[0] = L.r[low];
    	while (low < high)
    	{
        
    		while (high > low && L.r[high] >= L.r[0])
    			high--;
    		L.r[low] = L.r[high];
    		while (low < high && L.r[low] <= L.r[0])
    			low++;
    		L.r[high] = L.low;
    	}
    	L.r[low] = L.r[0];
    	return low;
    }
    void QSort(SqList &L, int low, int high)
    {
        
    	if (low >= high) return ;
    	else
    	{
        
    		pivoLoc = Partition(L, low, high);
    		QSort(L, low, pivoLoc - 1);
    		Q.Sort(l, pivoLoc + 1, high);
    	}
    }

3 总结与推广

发表评论取消回复

表情：

评论列表（有 0 条评论，103人围观）

还没有评论，来说两句吧...

相关阅读

相关作业24-归并排序与基数排序(防止题目重复)

1-3 对N个记录进行归并排序，归并趟数的数量级是O(NlogN)。() \[解析\]归并的数量级在O(logN)? 每上下相邻的两层之间,从上层到下层的过程就是一

太过爱你忘了你带给我的痛/ 2022年12月28日 00:44/ 0 赞/ 194 阅读

相关归并排序(MergeSort)(防止标题重复)

归并排序(MergeSort) 1 归并排序原理分解成最小的记录块(长度为0或1),必须要排序,就是有序块然后再归并 2 归并排序算法的实现 //

我会带着你远行/ 2022年12月27日 07:58/ 0 赞/ 150 阅读

相关堆排序-笔记(防止标题重复)

选择类排序简单选择排序:每一趟选出当前最小的记录, 将其交换到无序块的最前面. 如此,无序块逐渐变小,N-1 趟完成 (贪心,递归,动态规划) 引入:每一趟选择

迈不过友情╰/ 2022年12月27日 07:57/ 0 赞/ 131 阅读

相关快速排序-笔记(防止题目重复)

快速排序冒泡排序每次循环,相邻两元素两两比较,不符合则交换,最大元素沉底 //随便写的,好像不对 void BmbleSort(SqList &L)

野性酷女/ 2022年12月27日 07:50/ 0 赞/ 104 阅读

相关希尔排序-笔记(防止题目重复)

希尔排序子序列内部移动依次可能会消除多个逆序对(同时造成排序的不稳定) 1 算法思想设一个递减的增量序列如\{5, 3, 1\} 每一趟都将序列分成若干子

末蓝、/ 2022年12月27日 07:47/ 0 赞/ 124 阅读

相关作业8-栈与递归(防止题目重复)

2-1 令P代表入栈，O代表出栈。若利用堆栈将中缀表达式3\2+8/4 转为后缀表达式，则相应的堆栈操作序列是：© A.PPPOOO B.POPOPO C.

野性酷女/ 2022年12月27日 01:19/ 0 赞/ 212 阅读

相关作业7-栈及其应用(防止题目重复)

1-1 通过对堆栈S操作：Push(S,1), Push(S,2), Pop(S), Push(S,3), Pop(S), Pop(S)。输出的序列为：123。(F)

Bertha 。/ 2022年12月26日 15:28/ 0 赞/ 146 阅读

相关算法的时间复杂度和空间复杂度(防止题目重复)

1-1 算法分析的两个主要方面是时间复杂度和空间复杂度的分析。(T) 1-2 N2logN和NlogN2具有相同的增长速度(F) \[解析\]一个N^2logN

秒速五厘米/ 2022年12月24日 13:59/ 0 赞/ 106 阅读

相关关键路径(防止题目重复)

DAG(Directed AcyclineGraph) 有向无环图用来描述一个工程或系统的进行过程。一个工程可以分为若干个子工程，只有完成了这些子工程，就可以

超、凢脫俗/ 2022年12月18日 13:57/ 0 赞/ 199 阅读

相关 java 快速排序笔记

算法思想： 1. 在给定序列中找一个基准值，一般为区间的最左边的元素，记为 baseValue。 2. 序列中大于 baseValue 的元素均放在其右边。 3. 序列

我不是女神ヾ/ 2022年10月05日 11:52/ 0 赞/ 139 阅读