精华内容
下载资源
问答
  • 快速排序程序流程图
    千次阅读
    2021-09-27 14:34:42

    前言

    前面两篇文章我们已经分析了经典排序算法中的冒泡排序和插入排序的思路,以及冒泡排序的优化方案。接下来我们将继续学习一个新的排序算法 - 快速排序(二分法排序)。

    思路分析

    所谓的快速排序其实就是利用二分法加递归的原理,每次取出数组中的中间位置的值作为参照,然后再借助两个额外的数组。遍历原数组中的每个元素跟中间值(参照值)进行比较,把小于中间值的元素放在一个新数组中,相反把大于中间值的元素放在另一个新的数组中。这样一来其中一个新数组中的所有元素肯定都是小于中间值的,而另外一个新数组中的元素也必然都是大于中间值的。以此类推在把两个新的数组以同样的方式(可以采用递归)进行拆解,直到数组中只剩下一个元素为止,最后再把所有的小数组加所有的中间数再加上所有的大数组拼接在一起,就能得到我们想要的结果了。
    下面用一个实际例子来具体分析一下: 数组nums:[12,1,8,10,21,25,4,30,6]

    • 计算当前数组中的中间元素,mid:21, midIndex:4
    • 遍历数组nums将大于21的元素放在新数组right中,小于21的则放在新数组left中,得到left:[12,1,8,10,4,6],right:[25,30]
    • 按照上面的方法继续将新数组left和right进行二分法拆解
      • left数组中间值:10,left1:[1,8,4,6] ,right1:[12](当数组中只剩一个元素时不再进行拆分)
      • right数组中间值:30,left2:[25],right2: []
    • 现在只有left1中的元素个数还是大于1的,所以要继续拆分
      • left1数组中间值:4,left3:[1](不再拆分),right3:[8,6]
    • right3继续拆分:中间值:6,left4:[],right4:[8]
    • 到此已经全部拆分完毕,最后再将所有的left,mid和right合并在一起就是我们想要的结果了
    • 下面我们用一张图片来更直观的展示一下拼接过程:
      在这里插入图片描述

    快排代码

    var midSort = function midSort(nums){
    	if(nums.length <=1) return nums;
    	let mid = Math.floor(nums.length/2),
    		midNum = nums.splice(mid,1)[0];
    	let left = [], right = [];
    	nums.forEach(item =>{
    		item < midNum ? left.push(item): right.push(item)
    	})
    	return midSort(left).concat(midNum,midSort(right));//利用递归对left和right数组继续拆分
    }
    

    总结

    本文我们学习了经典排序算法中的快排法,该算法相对于冒泡和插入排序效率要高一些,但依然不算是最优算法。
    欢迎喜欢的老铁点赞,评论,加关注哦。

    更多相关内容
  • [图解] 快速排序

    千次阅读 2021-03-08 04:31:41
    1. 经典快速排序图示过程(1) 经典快速排序的总体流程(2) 根据基准值分区的过程2. 随机快速排序经典快速排序总是指定数组或者某部分的最后一个元素作为基准值,随机快速排序指定数组或者某一部分中的随机值作为基准值...

    1. 经典快速排序图示过程

    (1) 经典快速排序的总体流程

    a68f72278f8f

    (2) 根据基准值分区的过程

    2. 随机快速排序

    经典快速排序总是指定数组或者某部分的最后一个元素作为基准值,随机快速排序指定数组或者某一部分中的随机值作为基准值。

    3. 动图展示

    a68f72278f8f

    quickSort.gif

    4. 随机快速排序Java代码实现

    /**

    * 快速排序,使得整数数组 arr 有序

    */

    public static void quickSort(int[] arr) {

    if (arr == null || arr.length < 2) {

    return;

    }

    quickSort(arr, 0, arr.length - 1);

    }

    /**

    * 快速排序,使得整数数组 arr 的 [L, R] 部分有序

    */

    public static void quickSort(int[] arr, int L, int R) {

    if(L < R) {

    // 把数组中随机的一个元素与最后一个元素交换,这样以最后一个元素作为基准值实际上就是以数组中随机的一个元素作为基准值

    swap(arr, new Random().nextInt(R - L + 1) + L, R);

    int[] p = partition(arr, L, R);

    quickSort(arr, L, p[0] - 1);

    quickSort(arr, p[1] + 1, R);

    }

    }

    /**

    * 分区的过程,整数数组 arr 的[L, R]部分上,使得:

    * 大于 arr[R] 的元素位于[L, R]部分的右边,但这部分数据不一定有序

    * 小于 arr[R] 的元素位于[L, R]部分的左边,但这部分数据不一定有序

    * 等于 arr[R] 的元素位于[L, R]部分的中间

    * 返回等于部分的第一个元素的下标和最后一个下标组成的整数数组

    */

    public static int[] partition(int[] arr, int L, int R) {

    int basic = arr[R];

    int less = L - 1;

    int more = R + 1;

    while(L < more) {

    if(arr[L] < basic) {

    swap(arr, ++less, L++);

    } else if (arr[L] > basic) {

    swap(arr, --more, L);

    } else {

    L++;

    }

    }

    return new int[] { less + 1, more - 1 };

    }

    /*

    * 交换数组 arr 中下标为 i 和下标为 j 位置的元素

    */

    public static void swap(int[] arr, int i, int j) {

    int temp = arr[i];

    arr[i] = arr[j];

    arr[j] = temp;

    }

    5. 复杂度

    时间复杂度:O(nlogn)

    空间复杂度:快速排序使用递归,递归使用栈,因此它的空间复杂度为O(logn)

    稳定性:快速排序无法保证相等的元素的相对位置不变,因此它是不稳定的排序算法

    展开全文
  • 利用汇编语言实现快速排序,汇编语言排序算法。 数字逻辑与处理器大作业,通过汇编实现文件读入,快速排序,再写到文件中 汇编 快排 数逻
  • 快速排序程序 绝对原创 老师布置的作业 欢迎大家下载
  • 快速排序及优化方案

    千次阅读 2022-02-20 18:31:36
    快速排序流程2. 快速排序的实现时间复杂度计算3. 快速排序优化随机获取基准值进行优化3.2二路快速排序原理:思想:4. 总结 快速排序及其优化方案 1. 快速排序流程 首先设定一个分界值,通过该分界值将数组分成...

    快速排序

    1. 快速排序的流程

    • 首先设定一个分界值,通过该分界值将数组分成左右两部分。
    • 将大于分界值的数据集中到数组右边,小于分界值的数据集中到数组的左边,而等于分分界值的部分放在相对中间的部分。此时,左边部分中各元素都小于分界值,而右边部分中各元素都大于分界值,相对中间的部分的的数据等于分界值。
    • 然后,左边和右边的数据可以独立排序。对于左侧的数组数据,又可以取一个分界值,将该部分数据分成左右两部分,同样在左边放置较小值,右边放置较大值。右侧的数组数据也可以做类似处理。
    • 重复上述过程,可以看出,这是一个递归定义。通过递归将左侧部分排好序后,再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后,整个数组的排序也就完成了。

    2. 快速排序的实现

    原始的快速排序相对来说会比较熟悉点,大致的部分流程图如图所示:
    在这里插入图片描述
    直接上代码:

    #include<iostream>
    #include<string>
    #include<vector>
    #include<time.h>
    using namespace std;
    
    //三色旗原理代码部分
    pair<int, int> Quick(vector<int>& vec, int L, int R)
    {
    
    	int temp = vec[L];//基准值
    	int i = L - 1;//左边界
    	int j = R + 1;//右边界
    	int index = L;//交换变量
    	while (index < j)
    	{
    		if (vec[index] < temp)
    		{
    			swap(vec[index++], vec[++i]);
    		}
    		else if (vec[index] > temp)
    		{
    			swap(vec[index], vec[--j]);
    		}
    		else
    		{
    			index++;
    		}
    	}
    	pair<int, int> p = make_pair(i, j);//存储下次排序的左右边界,
    	return p;
    }
    
    void Quick_sort(vector<int>& vec, int L, int R)
    {
    	if (L >= R)return;//递归结束的标志
    	pair<int, int> p = Quick(vec, L, R);
    
    	Quick_sort(vec, L, p.first);//将数组的左部分进行排序
    	Quick_sort(vec, p.second, R);//将数组的右部分进行排序
    
    }
    int main()
    {
    	vector<int> vec = { 5,6,3,7,2,8 };
    	Quick_sort(vec, 0, vec.size() - 1);
    	for (auto it : vec)
    	{
    		cout << it << " ";
    	}
    	return 0;
    }
    

    时间复杂度计算

    快速排序的最优的情况时的时间复杂度为O(N*logN)
    因为最优解在排序过程中每次都利用递归将数组不断二分,并且不断二分过程次相当于二分法,而二分的时间复杂度为logN(这里的log是以2为底的),每次二分的各个子数组的和均为n个元素,在排序过程中所有元素在不同的递归过程中均会被遍历比较,所以每次都会有N个元素会被遍历,即时间复杂度为:O(N*logN)
    最坏的情况时的时间复杂度为O(N^2)
    这种情况是当数组有序的情况下,每次基准值都是取了数组中的最小值或最大值,而且每次递归都只是排除了基准值那个元素,这里就很像冒泡排序不断将子数组中最值排除掉,而冒泡排序的时间复杂度为O(N^2)。
    因此最坏情况下的时间复杂度为O(N^2)。

    3. 快速排序优化

    3.1 随机获取基准值进行优化

    上一节我们自己动手写的一个快速排序的算法,在进行毫无规则的数组排序过程中表现得非常好,但是,当我们去百万,十万级别量的数据进行排序并且高度的有序化时,我们会发现此时程序运行的过程中,发现快速排序的效率变得异常的低下,会比相同数据量的数组中的数据是毫无规则时效率低得多了,近似退回了O(n^2)的复杂度,而此时程序则需要等待非常长的时间才能执行完全。
    在编写快排代码的过程中,我们是利用递归来对数组进行划分的,这和归并排序里面的利用递归使得不断的二分才能达到O(n*logn)的时间复杂度相似,在快速排序中最好的情况就是如同归并一样,每次都是二分,这种情况的时间复杂度是最佳的时间复杂度O(n*logn)。如图:
    在这里插入图片描述

    但是当数组高度有序化或者数组本来就是有序的时候,这个时候数组数据呈现出一边倒的趋势此时快速排序的时间复杂度达到最坏的情况逼近O(n^2)
    甚至达到为O(n^2),这样的快速排序远远达不到我们的需求,如图:
    在这里插入图片描述

    在这种情况下我们可以通过随机获取每次排序的基准值来进行优化int temp = vec[rand()%(R-L+1)+L];,同时通过百万、十万级别量的数据量来计算程序运行的时间比较时间复杂度。
    计算时间的代码如下:

    clock_t startime, endtime;
    	startime = clock();
        ....//中间代码
    	endtime = clock();
    	cout << (double)(endtime - startime)/ CLOCKS_PER_SEC << endl;
    

    通过随机获取基准值优化代码如下:

    #include<iostream>
    #include<string>
    #include<vector>
    #include<time.h>
    using namespace std;
    
    //三色旗原理代码部分
    pair<int, int> Quick(vector<int>& vec, int L, int R)
    {
    
    	int temp = vec[rand()%(R-L+1)+L];//随机获取基准值进行优化
    	//int temp = vec[L];//没有获取随机基准值
    	int i = L - 1;//左边界
    	int j = R + 1;//右边界
    	int index = L;//交换变量
    	while (index < j)
    	{
    		if (vec[index] < temp)
    		{
    			swap(vec[index++], vec[++i]);
    		}
    		else if (vec[index] > temp)
    		{
    			swap(vec[index], vec[--j]);
    		}
    		else
    		{
    			index++;
    		}
    	}
    	pair<int, int> p = make_pair(i, j);//存储下次排序的左右边界,
    	return p;
    }
    
    void Quick_sort(vector<int>& vec, int L, int R)
    {
    	if (L >= R)return;//递归结束的标志
    	pair<int, int> p = Quick(vec, L, R);
    
    	Quick_sort(vec, L, p.first);//将数组的左部分进行排序
    	Quick_sort(vec, p.second, R);//将数组的右部分进行排序
    
    }
    int main()
    {
    	clock_t startime, endtime;
    	startime = clock();//开始时间
    
    	vector<int> vec;
    	for (int i = 0; i < 100000; i++) {
    	//(在这里使用十万级别的数据量 完全有序的数组进行计算时间复杂度 百万级别的数据量由于程序执行时间太长 不例举)
    		vec.push_back(i);
    	}
    	Quick_sort(vec, 0, vec.size() - 1);
    	/*for (auto it : vec)//在这里不进行输出,数据量太大
    	{
    		cout << it << " ";
    	}*/
    	endtime = clock();//结束时间
    	cout << (double)(endtime - startime)/ CLOCKS_PER_SEC << endl;
    	//在这里没有定义单位,只通过数值进行比较来判断
    	return 0;
    }
    

    此时没有经过优化的代码执行时间如图:
    在这里插入图片描述

    经过优化的代码执行时间如图:
    在这里插入图片描述

    两者相对比较而言进行优化的时间复杂度远远小于未经过优化的。但是在数组里面的数据是乱序的情况下,经过优化的时间复杂度会偶尔出现略高于未经过优化的情况,但影响并不是很大。

    3.2二路快速排序

    接着前面所介绍来说,当我们排序的是一个近乎有序的序列时,快速排序会退化到一个O(n^2) 级别的排序算法,而我们对此的就是引入了随机化快速排序算法;但是问题又来了,当我们排序的数据是一个数值重复率非常高的序列时,或者是输入的数据完全相同的情况时,此时随机化快速排序算法就不再起作用了,而将会再次退化为一个O(n^2) 级别的排序算法。
    在这种情况下不管是>=temp还是<=temp,当我们的序列中存在大量重复的元素时,排序完成之后就会将整个数组序列分成两个极度不平衡的部分,甚至更恶劣的情况是所有数据均一样而出现一边倒的趋势,所以又退化到了O(n^2) 级别的时间复杂度,这是因为对于每一个"基准"元素来说,重复的元素太多了,如果我们选的"基准"元素稍微有一点的不平衡,那么就会导致两部分的差距非常大;即时我们的"基准"元素选在了一个平衡的位置,但是由于等于"基准"元素的元素也非常多,也会使得序列被分成两个及其不平衡的部分,那么在这种情况下快速排序就又会退化成O(n^2) 级别的排序算法。
    在这里我们可以使用二路快速排序进行优化。

    原理:

    前面所叙述的快速排序算法是将>temp和<temp两个部分元素都放在索引值i所指向的位置的左边部分,而双路快速排序则是使用两个索引值(i、j)用来遍历我们的序列,将<temp的元素放在索引 i 所指向位置的左边,而将>temp的元素放在索引j所指向位置的右边。

    思想:

    1、首先从左边的i索引往右边遍历,如果i指向的元素<temp,那直接将i++移动到下一个位置,直道i指向的元素>=temp则停止。
    2、然后使用j索引从右边开始往左边遍历,如果j指向的元素>temp,那直接将j–移动到下一个位置,直道j指向的元素<=temp则停止
    3、此时i之前的元素都已经归并为<temp的部分了,而j之后的元素也都已经归并为>temp的部分了,此时只需要将vec[i]和vec[j]交换位置即可。这样就可以避免出现=temp的元素全部集中在某一个部分,这正是双路排序算法的一个核心。但是当需要排序的数据长度比较小时,此时使用插入排序的性能比较好,所以我们结合快速排序和插入排序进行一个优化快速排序。
    在这里插入图片描述
    具体实现代码:

    #include<iostream>
    #include<vector>
    #include<time.h>
    using namespace std;
    void Insert_sort(vector<int>& vec,int L,int R) {
        for (int i = L+1; i < R; i++) {//用i来记录无序表的第一个值的下标
            int j = i - 1;//用来记录前面有序列的最后一个值的下标
            int temp = vec[i];//记录无序列的第一个值的值
            for (; j >= 0; j--) {
                if (vec[j] > temp) {
                    vec[j + 1] = vec[j];//将有序表中的元素后移。
                }
                else {
                    break;//当无序表中的第一个值不比有序表中的最后一个值小时,跳出循环
                }
            }
            vec[j + 1] = temp;//将后移后的空值补上无序表中的第一个值。
        }
    }
    int qucikSort(vector<int>& vec, int L, int R)
    {
        swap(vec[L], vec[rand() % (R - L + 1) + L]);// 随机产生"基准"元素所在位置,并与第一个元素交换位置
        int temp = vec[L]; // 将第一个元素作为"基准"元素
        // 使用i索引从左到右遍历,使用j索引从右到左遍历
        int i = L + 1;// 索引值i初始化为第二个元素位置
        int j = R;// 索引值j初始化为最后一个元素位置
        while (true) {
            while ((i < R) && (vec[i] < temp)) i++;// 使用索引i从左往右遍历直到 vec[i] < temp
            while ((j > L + 1) && (vec[j] > temp)) j--;// 使用索引j从右往左遍历直到 vec[j] > temp
            if (i >= j) break;// 退出循环的条件
            swap(vec[i], vec[j]);// 将 vec[i] 与 vec[j] 交换位置
            i++;
            j--;
        }
        swap(vec[L], vec[j]);// 最后将"基准"元素temp放置到合适的位置
        return j;
    }
    void quick(vector<int>& vec, int L, int R)
    {
        if (R - L <= 40) {//当数据量比较小时我们采用插入排序进行
            Insert_sort(vec, L, R);
            return;
        }
        int p = qucikSort(vec, L, R);// 对vec[left...right]区间元素进行排序操作,找到"基准"元素
        quick(vec, L, p - 1);// 对基准元素之前的序列递归
        quick(vec, p + 1, R);// 对基准元素之后的序列递归
    }
    
    int main()
    {
        clock_t startime, endtime;
        startime = clock();//开始时间
    
        vector<int> vec;
        srand(time(0));
        for (int i = 0; i < 100000; i++) {
        //(在这里使用十万级别的数据量,完全有序的数组进行计算时间复杂度
        // 百万级别的数据量由于程序执行时间太长,不例举)
            vec.push_back(rand()%100);
        }
        quick(vec, 0, vec.size() - 1);
        //for (auto it : vec)//在这里不进行输出,数据量太大
        //{
        //    cout << it << " ";
        //}
        endtime = clock();//结束时间
        cout << (double)(endtime - startime) / CLOCKS_PER_SEC << endl;
        //在这里没有定义单位,只通过数值进行比较来判断
        return 0;
    }
    

    在这里随机数产生的数据进行性能分析,如图第一个数据是未经过优化的时执行一个利用随机生成数乱序并且重复率较高的执行时间,第二个数据是二路快速排序的执行时间。在这里执行时间相差不多是因为这里我们难以得到一个重复率非常高的一组数据,但是实际上双路快速排序优化的结果还是比较理想的。
    在这里插入图片描述

    4. 总结

    在上述优化的过程中, 对于原始的快排来说,当重复率低,并且数组的有序化低是具有很好的效率,但是在应对大量的规则性比较强的数据时,效率是跟不上。而随机快速排序只是获取了一个随机基准值来应对数据有序化程度比较高的情况下来进行优化。但是二路快速排序结合了随机快排和插入排序来应对能够出现的所有情况来 达到比较好的效果。

    投稿来自 东北石油大学 - 计科192 - 于银喜

    展开全文
  • 7中排序算法学习总结(图解+程序代码)

    千次阅读 多人点赞 2017-06-08 17:08:49
     一种是比较排序,时间复杂度O(nlogn) ~ O(n^2),主要有:冒泡排序,选择排序,插入排序,归并排序,堆排序,快速排序等。  另一种是非比较排序,时间复杂度可以达到O(n),主要有:计数排序,基数排序,桶排序等...

    我们通常所说的排序算法往往指的是内部排序算法,即数据记录在内存中进行排序。

      排序算法大体可分为两种:

        一种是比较排序,时间复杂度O(nlogn) ~ O(n^2),主要有:冒泡排序选择排序插入排序归并排序堆排序快速排序等。

        另一种是非比较排序,时间复杂度可以达到O(n),主要有:计数排序基数排序桶排序等。


    常用排序算法的时间复杂度:


    这里介绍一下稳定性的概念。如果原序列中有A1 = A2,排序前A1在A2的前面,排序后A1仍然在A2的前面,则说明这种排序算法是稳定的。否则不稳定。

    并不是说冒泡排序法就一直是稳定的,如果程序代码中有a[i]>=a[i+1]则交换顺序的语句,就将会把原来相等的数值交换位置,则冒牌排序算法就变为不稳定的了。反过来不稳定的排序算法也可以变成稳定的。

    现再开始通过程序代码和图解的方式介绍各种常用的排序算法

    一、冒泡排序法

    算法思想

      冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错-误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

    步骤:

    1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
    2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
    3. 针对所有的元素重复以上的步骤,除了最后一个。
    4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
    算法流程图:

    冒泡排序动态效果:


    算法实现:

    /*冒泡排序法*/
    // 分类 -------------- 内部比较排序
    // 数据结构 ---------- 数组
    // 最差时间复杂度 ---- O(n^2)
    // 最优时间复杂度 ---- 如果序列在一开始已经大部分排序过的话,会接近O(n)
    // 平均时间复杂度 ---- O(n^2)
    // 所需辅助空间 ------ O(1)
    // 稳定性 ------------ 稳定
    
    #include <stdio.h>
    void Bubble_sort(int *a,int n)
    {
        int i,j;
        for(i = 0;i<n;i++)
        {
            for(j = 0;j < n-i-1;j++)
            {
                if(a[j] > a[j+1])
                {
                    int temp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = temp;
                }
            }
        }
    }
    int main(int argc ,char *argv[])
    {
        int i;
        int array[10] = {13,58,61,43,97,6,1,84,66,31};
        printf("排序后的数组为:");
        Bubble_sort(array,10);//调用冒泡排序函数,传入数组名和数组长度
        for(i = 0;i<sizeof(array)/sizeof(int);i++)//这里可使用sizeof来求出数组长度
            printf("%d  ",array[i]);
        return 0;
    }
    


    1. 二、简单选择排序——选择排序法

    2. 算法思想:
    3. 在要排序的一组数中,选出最小(或者最大)的个数与第1个位置的数交换;然后在剩下的数当中再找最小(或者最大)的与第2个位置的数交换,依次类推,直到第n-1个元素(倒数第二个数)和第n个元素(最后个数)比较为止。
    步骤:

    第一趟,从n 个记录中找出关键码最小的记录与第一个记录交换;

    第二趟,从第二个记录开始的n-1 个记录中再选出关键码最小的记录与第二个记录交换;

    以此类推.....

    第i 趟,则从第i 个记录开始的n-i+1 个记录中选出关键码最小的记录与第i 个记录交换,

    直到整个序列按关键码有序。


    算法流程图:

    选择排序动态效果:

    视觉直观感受7种常用排序算法

    算法实现:

    /*选择排序法*/
    // 分类 -------------- 内部比较排序
    // 数据结构 ---------- 数组
    // 最差时间复杂度 ---- O(n^2)
    // 最优时间复杂度 ---- O(n^2)
    // 平均时间复杂度 ---- O(n^2)
    // 所需辅助空间 ------ O(1)
    // 稳定性 ------------ 不稳定
    
    #include <stdio.h>
    void Selection_sort(int *a,int n)
    {
        int i,j,k;
        for(i = 0 ; i < n-1 ; i++)
        {
            k = i;
            for(j = i+1 ; j < n ; j++)
            {
                if(a[k] > a[j])
                    k = j;  //找出最小值的数组下标
            }
            if(k != i)  //如果最小值的下标和要交换的位置下标不相等,就交换位置
            {
                int temp = a[k];
                a[k] = a[i];
                a[i] = temp;
            }
        }
    }
    int main(int argc ,char *argv[])
    {
        int i;
        int array[10] = {8, 5, 2, 6, 9, 3, 1, 4, 0, 7};
        printf("排序后的数组为:");
        Selection_sort(array,10);//调用冒泡排序函数,传入数组名和数组长度
        for(i = 0;i<sizeof(array)/sizeof(int);i++)//这里可使用sizeof来求出数组长度
            printf("%d  ",array[i]);
        return 0;
    }
    
    
    算法实现过程动态图示:




    三、直接插入排序

    算法思想:

    插入排序是一种简单直观的排序算法。它的工作原理非常类似于我们抓扑克牌

          

     

      对于未排序数据(右手抓到的牌),在已排序序列(左手已经排好序的手牌)中从后向前扫描,找到相应位置并插入。

      插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

    步骤:

    1. 从第一个元素开始,该元素可以认为已经被排序
    2. 取出下一个元素,在已经排序的元素序列中从后向前扫描
    3. 如果该元素(已排序)大于新元素,将该元素移到下一位置
    4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
    5. 将新元素插入到该位置后
    6. 重复步骤2~5
    算法流程图:


    插入排序动态效果:


    算法实现:

    /*简单插入排序*/
    // 分类 ------------- 内部比较排序
    // 数据结构 ---------- 数组
    // 最差时间复杂度 ---- 最坏情况为输入序列是降序排列的,此时时间复杂度O(n^2)
    // 最优时间复杂度 ---- 最好情况为输入序列是升序排列的,此时时间复杂度O(n)
    // 平均时间复杂度 ---- O(n^2)
    // 所需辅助空间 ------ O(1)
    // 稳定性 ------------ 稳定
    
    #include <stdio.h>
    void Insertion_sort(int *a, int n)
    {
        int i,j,get;
        for (i = 1; i < n; i++)             // 类似抓扑克牌排序
        {
            get = a[i];                     // 右手抓到一张扑克牌
            j = i - 1;                      // 拿在左手上的牌总是排序好的
            while (j >= 0 && a[j] > get)    // 将抓到的牌与手牌从右向左进行比较
            {
                a[j + 1] = a[j];            // 如果该手牌比抓到的牌大,就将其右移
                j--;
            }
            a[j + 1] = get;// 直到该手牌比抓到的牌小(或二者相等),将抓到的牌插入到该手牌右边(相等元素的相对次序未变,所以插入排序是稳定的)
        }
    }
    
    int main(int argc,char *argv[])
    {
        int i;
        int array[8] = {6, 5, 3, 1, 8, 7, 2, 4};
        Insertion_sort(array,8);
        printf("插入排序后的数组:\n");
        for(i = 0;i<sizeof(array)/sizeof(int);i++)
        {
             printf("%d  ",array[i]);
        }
        return 0;
    }
    


    算法实现过程动态图示:


    四、插入排序——希尔排序

    算法思想:

    希尔排序,也称递减增量排序算法,是插入排序的一种高速而稳定的改进版本。

    希尔排序是基于插入排序的以下两点性质而提出改进方法的:

    1、插入排序在对几乎已经排好序的数据操作时, 效率高, 即可以达到线性排序的效率

    2、但插入排序一般来说是低效的, 因为插入排序每次只能将数据移动一位>

    先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行依次直接插入排序。

    步骤:

    1. 选择一个增量序列t1,t2,…,tk,其中ti>tj,tk=1;
    2. 按增量序列个数k,对序列进行k 趟排序;
    3. 每趟排序,根据对应的增量ti,将待排序列分割成若干长度为m 的子序列,分别对各子表进行直接插入排序。仅增量因子为1 时,整个序列作为一个表来处理,表长度即为整个序列的长度
    算法流程图:

    希尔排序动态效果:
    视觉直观感受7种常用排序算法

    算法实现:
    /*希尔排序法*/
    // 分类 -------------- 内部比较排序
    // 数据结构 ---------- 数组
    // 最差时间复杂度 ---- 根据步长序列的不同而不同。已知最好的为O(n(logn)^2)
    // 最优时间复杂度 ---- O(n)
    // 平均时间复杂度 ---- 根据步长序列的不同而不同。
    // 所需辅助空间 ------ O(1)
    // 稳定性 ------------ 不稳定
    
    #include <stdio.h>
    void Shell_sort(int *a,int n)
    {
        int i,j,h = 0,get;
        while (h <= n)                          // 生成初始增量
        {
            h = 3*h + 1;
        }
        while (h >= 1)
        {
            for (i = h; i < n; i++)
            {
                j = i - h;
                get = a[i];
                while ((j >= 0) && (a[j] > get))
                {
                    a[j + h] = a[j];
                    j = j - h;
                }
                a[j + h] = get;
            }
            h = (h - 1) / 3;                    // 递减增量
        }
    }
    
    int main(int argc,char *argv[])
    {
        int i;
        int array[10] = {13,58,61,43,97,6,1,84,66,31};
        Shell_sort(array,10);
        printf("希尔排序后的数组为:\n");
        for(i = 0;i<sizeof(array)/sizeof(int);i++)
            printf("%d  ",array[i]);
        return 0;
    }
    


    希尔排序是不稳定的排序算法,虽然一次插入排序是稳定的,不会改变相同元素的相对顺序,但在不同的插入排序过程中,相同的元素可能在各自的插入排序中移动,最后其稳定性就会被打乱。

      比如序列:{ 3, 5, 10, 8, 7, 2, 8, 1, 20, 6 },h=2时分成两个子序列 { 3, 10, 7, 8, 20 } 和  { 5, 8, 2, 1, 6 } ,未排序之前第二个子序列中的8在前面,现在对两个子序列进行插入排序,得到 { 3, 7810, 20 } 和 { 12568 } ,即 { 3, 1, 7, 2, 8, 5, 10, 6, 20, 8 } ,两个8的相对次序发生了改变。

    五、选择排序——堆排序
    算法思想:
    堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构(通常堆是通过一维数组来实现的),并同时满足堆的性质:即子结点的键值总是小于(或者大于)它的父节点。

    堆的定义如下:具有n个元素的序列(k1,k2,...,kn),当且仅当满足


    时称之为堆。由堆的定义可以看出,堆顶元素(即第一个元素)必为最小项(小顶堆)。
    若以一维数组存储一个堆,则堆对应一棵完全二叉树,且所有非叶结点的值均不大于(或不小于)其子女的值,根结点(堆顶元素)的值是最小(或最大)的。如:

    (a)大顶堆序列:(96, 83,27,38,11,09)

      (b)  小顶堆序列:(12,36,24,85,47,30,53,91)



    初始时把要排序的n个数的序列看作是一棵顺序存储的二叉树(一维数组存储二叉树),调整它们的存储序,使之成为一个堆,将堆顶元素输出,得到n 个元素中最小(或最大)的元素,这时堆的根节点的数最小(或者最大)。然后对前面(n-1)个元素重新调整使之成为堆,输出堆顶元素,得到n 个元素中次小(或次大)的元素。依此类推,直到只有两个节点的堆,并对它们作交换,最后得到有n个节点的有序序列。称这个过程为堆排序

    因此,实现堆排序需解决两个问题:
    1. 如何将n 个待排序的数建成堆;
    2. 输出堆顶元素后,怎样调整剩余n-1 个元素,使其成为一个新堆。

    首先讨论第二个问题:输出堆顶元素后,对剩余n-1元素重新建成堆的调整过程。
    调整小顶堆的方法:

    1)设有m 个元素的堆,输出堆顶元素后,剩下m-1 个元素。将堆底元素送入堆顶((最后一个元素与堆顶进行交换),堆被破坏,其原因仅是根结点不满足堆的性质。

    2)将根结点与左、右子树中较小元素的进行交换。

    3)若与左子树交换:如果左子树堆被破坏,即左子树的根结点不满足堆的性质,则重复方法 (2).

    4)若与右子树交换,如果右子树堆被破坏,即右子树的根结点不满足堆的性质。则重复方法 (2).

    5)继续对不满足堆性质的子树进行上述交换操作,直到叶子结点,堆被建成。

    称这个自根结点到叶子结点的调整过程为筛选。如图:



    再讨论对n 个元素初始建堆的过程。
    建堆方法:对初始序列建堆的过程,就是一个反复进行筛选的过程。

    1)n 个结点的完全二叉树,则最后一个结点是第n/2个结点的子树。

    2)筛选从第n/2个结点为根的子树开始,该子树成为堆。

    3)之后向前依次对各结点为根的子树进行筛选,使之成为堆,直到根结点。

    如图建堆初始过程:无序序列:(49,38,65,97,76,13,27,49)    



    步骤:

    1. 创建一个堆
    2. 把堆顶元素(最大值)和堆尾元素互换
    3. 把堆的尺寸缩小1,并调用heapify(A, 0)从新的堆顶元素开始进行堆调整
    4. 重复步骤2,直到堆的尺寸为1
    堆排序动态效果:

    算法实现:

    /*堆排序算法*/
    // 分类 -------------- 内部比较排序
    // 数据结构 ---------- 数组
    // 最差时间复杂度 ---- O(nlogn)
    // 最优时间复杂度 ---- O(nlogn)
    // 平均时间复杂度 ---- O(nlogn)
    // 所需辅助空间 ------ O(1)
    // 稳定性 ------------ 不稳定
    
    #include <stdio.h>
    int heapsize;    // 堆大小
    
    void exchange(int A[], int i, int j)    // 交换A[i]和A[j]
    {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
    
    void heapify(int A[], int i)            // 堆调整函数(这里使用的是最大堆)
    {
        int leftchild = 2 * i + 1;          // 左孩子索引
        int rightchild = 2 * i + 2;         // 右孩子索引
        int largest;                        // 选出当前结点与左右孩子之中的最大值
        if (leftchild < heapsize && A[leftchild] > A[i])
            largest = leftchild;
        else
            largest = i;
        if (rightchild < heapsize && A[rightchild] > A[largest])
            largest = rightchild;
        if (largest != i)
        {
            exchange(A, i, largest);        // 把当前结点和它的最大(直接)子节点进行交换
            heapify(A, largest);            // 递归调用,继续从当前结点向下进行堆调整
        }
    }
    
    void buildheap(int A[], int n)          // 建堆函数
    {
        int i;
        heapsize = n;
        for ( i = heapsize / 2 - 1; i >= 0; i--) // 对每一个非叶结点
            heapify(A, i);                  // 不断的堆调整
    }
    
    void heapsort(int A[], int n)
    {
        int i;
        buildheap(A, n);
        for (i = n - 1; i >= 1; i--)
        {
            exchange(A, 0, i); // 将堆顶元素(当前最大值)与堆的最后一个元素互换(该操作很有可能把后面元素的稳定性打乱,所以堆排序是不稳定的排序算法)
            heapsize--;        // 从堆中去掉最后一个元素
            heapify(A, 0);     // 从新的堆顶元素开始进行堆调整
        }
    }
    
    int main()
    {
        int i;
        int A[] = { 5, 2, 9, 4, 7, 6, 1, 3, 8 };// 从小到大堆排序
        int n = sizeof(A) / sizeof(int);
        heapsort(A, n);
        printf("堆排序结果:");
        for (i = 0; i < n; i++)
        {
            printf("%d ", A[i]);
        }
        printf("\n");
        return 0;
    }
    


    堆排序是不稳定的排序算法,不稳定发生在堆顶元素与A[i]交换的时刻。

      比如序列:{ 9, 5, 7, 5 },堆顶元素是9,堆排序下一步将9和第二个5进行交换,得到序列 { 55, 7, 9 },再进行堆调整得到{ 7,55, 9 },重复之前的操作最后得到{ 55, 7, 9 }从而改变了两个5的相对次序。



    六、归并排序

    算法思想:

    归并排序是创建在归并操作上的一种有效的排序算法,效率为O(nlogn),1945年由冯·诺伊曼首次提出。

      归并排序的实现分为递归实现非递归(迭代)实现。递归实现的归并排序是算法设计中分治策略的典型应用,我们将一个大问题分割成小问题分别解决,然后用所有小问题的答案来解决整个大问题。非递归(迭代)实现的归并排序首先进行是两两归并,然后四四归并,然后是八八归并,一直下去直到归并了整个数组。

    归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

    步骤:

    1. 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
    2. 设定两个指针,最初位置分别为两个已经排序序列的起始位置
    3. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
    4. 重复步骤3直到某一指针到达序列尾
    5. 将另一序列剩下的所有元素直接复制到合并序列尾
    算法流程图:


    归并排序动态效果:


    算法实现:

    /*归并排序算法*/
    // 分类 -------------- 内部比较排序
    // 数据结构 ---------- 数组
    // 最差时间复杂度 ---- O(nlogn)
    // 最优时间复杂度 ---- O(nlogn)
    // 平均时间复杂度 ---- O(nlogn)
    // 所需辅助空间 ------ O(n)
    // 稳定性 ------------ 稳定
    
    #include <stdio.h>
    #include <limits.h>                // 包含极限值的头文件,这里用到了无穷大INT_MAX
    
    int L[10];    // 两个子数组定义成全局变量(辅助存储空间,大小正比于元素的个数)
    int R[10];
    
    void merge(int A[], int left, int middle, int right)// 合并两个已排好序的数组A[left...middle]和A[middle+1...right]
    {
        int i,j,k;
        int n1 = middle - left + 1;     // 两个数组的大小
        int n2 = right - middle;
        for (i = 0; i < n1; i++)    // 把两部分分别拷贝到两个数组中
            L[i] = A[left + i];
        for (j = 0; j < n2; j++)
            R[j] = A[middle + j + 1];
        L[n1] = INT_MAX;                // 使用无穷大作为哨兵值放在子数组的末尾
        R[n2] = INT_MAX;                // 这样可以免去检查某个子数组是否已读完的步骤
        i = 0;
        j = 0;
        for (k = left; k <= right; k++) // 依次比较两个子数组中的值,每次取出更小的那一个放入原数组
        {
            if (L[i] <= R[j])
            {
                A[k] = L[i];
                i++;
            }
            else
            {
                A[k] = R[j];
                j++;
            }
        }
    
    }
    
    void mergesort_recursion(int A[], int left, int right) // 递归实现的归并排序(自顶向下)
    {
        int middle = (left + right) / 2;
        if (left < right)          // 当待排序的序列长度为1时(left == right),递归“开始回升”
        {
            mergesort_recursion(A, left, middle);
            mergesort_recursion(A, middle + 1, right);
            merge(A, left, middle, right);
        }
    }
    
    void mergesort_iteration(int A[], int left, int right)  // 非递归(迭代)实现的归并排序(自底向上)
    {
        int size;
        int low, middle, high;    // 子数组索引,前一个为A[low...middle],后一个子数组为A[middle+1...high]
        for (size = 1; size <= right - left; size *= 2) // 子数组的大小初始为1,每轮翻倍
        {
            low = left;
            while (low + size - 1 <= right - 1 )// 后一个子数组存在(需要归并)
            {
                middle = low + size - 1;
                high = middle + size;
                if(high > right)// 后一个子数组大小不足size
                    high = right;
                merge(A, low, middle, high);    //合并
                low = high + 1;     //前一个子数组索引向后移动
            }
        }
    }
    
    int main()
    {
        int i;
        int A1[] = { 6, 5, 3, 1, 8, 7, 2, 4 };    // 从小到大归并排序
        int A2[] = { 6, 5, 3, 1, 8, 7, 2, 4 };
        int n1 = sizeof(A1) / sizeof(int);
        int n2 = sizeof(A2) / sizeof(int);
        mergesort_recursion(A1, 0, n1 - 1);       // 递归实现
        mergesort_iteration(A2, 0, n2 - 1);       // 非递归实现
        printf("递归实现的归并排序结果:");
        for (i = 0; i < n1; i++)
        {
            printf("%d ",A1[i]);
        }
        printf("\n");
        printf("非递归实现的归并排序结果:");
        for (i = 0; i < n2; i++)
        {
            printf("%d ", A2[i]);
        }
        printf("\n");
        return 0;
    }
    


    上述代码对序列{ 6, 5, 3, 1, 8, 7, 2, 4 }进行归并排序的实例如下 

     

         

    七、快速排序

    算法思想:

    快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序n个元素要O(nlogn)次比较。在最坏状况下则需要O(n^2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他O(nlogn)算法更快,因为它的内部循环可以在大部分的架构上很有效率地被实现出来。

    快速排序使用分治策略(Divide and Conquer)来把一个序列分为两个子序列。

    步骤:

    1. 从序列中挑出一个元素,作为"基准"(pivot).
    2. 把所有比基准值小的元素放在基准前面,所有比基准值大的元素放在基准的后面(相同的数可以到任一边),这个称为分区(partition)操作。
    3. 对每个分区递归地进行步骤1~3,递归的结束条件是序列的大小是0或1,这时整体已经被排好序了。
    算法流程图:



    快速排序法动态效果:


    算法实现:

    /*快速排序法*/
    // 分类 ------------ 内部比较排序
    // 数据结构 --------- 数组
    // 最差时间复杂度 ---- 每次选取的基准都是最大的元素(或者每次都是最小),导致每次只划分出了一个子序列,需要进行n-1次划分才能结束递归,时间复杂度为O(n^2)
    // 最优时间复杂度 ---- 每次选取的基准都能使划分均匀,只需要logn次划分就能结束递归,时间复杂度为O(nlogn)
    // 平均时间复杂度 ---- O(nlogn)
    // 所需辅助空间 ------ O(logn)~O(n),主要是递归造成的栈空间的使用(用来保存left和right等局部变量),取决于递归树的深度
    //                   一般为O(logn),最差为O(n)(基本有序的情况)
    // 稳定性 ---------- 不稳定
    
    #include <stdio.h>
    
    int quicksort(int v[], int left, int right) //传入数组的最低和最高的下标
    {
    	if(left < right)
    	{
    		int key = v[left];  //将数组最左边的值作为基准值用以比较
    		int low = left;
    		int high = right;
    		while(low < high)   //遍历数组
    		{
    			while(low < high && v[high] >= key)     //将大于等于基准值的值放在数组右边
    			{
    				high--;     //最高位数组下标自减
    			}
    			v[low] = v[high];   //如果高位下标的值小于基准值就放到数组左边
    			while(low < high && v[low] < key)   //将小于基准值的值放在数组左边
    			{
    				low++;      //最低位数组下标自增
    			}
    			v[high] = v[low];   //如果低位下标的值大于基准值就放到数组右边
    		}
            v[low] = key;   //最后将基准值放入数组
            quicksort(v,left,low-1);    //遍历调用排序函数
            quicksort(v,low+1,right);
    	}
    }
    
    int main(int argc, char *argv[])
    {
    
    	int array[10] = {8,1,4,2,10,3,5,9,7,6};
    	int i;
    	printf("快速排序后的数组为:");
    	quicksort(array,0,9);
    	for( i = 0; i < 10; i++ )
    		printf("%d ",array[i]);
        printf("\n");
    	return 0;
    }
    

    快速排序是不稳定的排序算法,不稳定发生在基准元素与A[tail+1]交换的时刻。

      比如序列:{ 1, 3, 4, 2, 8, 9, 8, 7, 5 },基准元素是5,一次划分操作后5要和第一个8进行交换,从而改变了两个元素8的相对次序。



    总结

    各种排序的稳定性,时间复杂度和空间复杂度总结:

     我们比较时间复杂度函数的情况:



                                 时间复杂度函数O(n)的增长情况


    所以对n较大的排序记录。一般的选择都是时间复杂度为O(nlog2n)的排序方法。


    时间复杂度来说:

    (1)平方阶(O(n2))排序
      各类简单排序:直接插入、直接选择和冒泡排序;
     (2)线性对数阶(O(nlog2n))排序
      快速排序堆排序归并排序
     (3)O(n1+§))排序,§是介于0和1之间的常数。

           希尔排序
    (4)线性阶(O(n))排序
      基数排序,此外还有桶、箱排序。

    说明:

    当原表有序或基本有序时,直接插入排序和冒泡排序将大大减少比较次数和移动记录的次数,时间复杂度可降至On);

    而快速排序则相反,当原表基本有序时,将蜕化为冒泡排序,时间复杂度提高为On2);

    原表是否有序,对简单选择排序、堆排序、归并排序和基数排序的时间复杂度影响不大。

     

    稳定性:

    排序算法的稳定性:若待排序的序列中,存在多个具有相同关键字的记录,经过排序, 这些记录的相对次序保持不变,则称该算法是稳定的;若经排序后,记录的相对 次序发生了改变,则称该算法是不稳定的。 
         稳定性的好处:排序算法如果是稳定的,那么从一个键上排序,然后再从另一个键上排序,第一个键排序的结果可以为第二个键排序所用。基数排序就是这样,先按低位排序,逐次按高位排序,低位相同的元素其顺序再高位也相同时是不会改变的。另外,如果排序算法稳定,可以避免多余的比较;

    稳定的排序算法:冒泡排序、插入排序、归并排序和基数排序

    不是稳定的排序算法:选择排序、快速排序、希尔排序、堆排序

     

    选择排序算法准则:

    每种排序算法都各有优缺点。因此,在实用时需根据不同情况适当选用,甚至可以将多种方法结合起来使用。

    选择排序算法的依据

    影响排序的因素有很多,平均时间复杂度低的算法并不一定就是最优的。相反,有时平均时间复杂度高的算法可能更适合某些特殊情况。同时,选择算法时还得考虑它的可读性,以利于软件的维护。一般而言,需要考虑的因素有以下四点:

    1.待排序的记录数目n的大小;

    2.记录本身数据量的大小,也就是记录中除关键字外的其他信息量的大小;

    3.关键字的结构及其分布情况;

    4.对排序稳定性的要求。

    设待排序元素的个数为n.

    1)当n较大,则应采用时间复杂度为O(nlog2n)的排序方法:快速排序、堆排序或归并排序序。

       快速排序:是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短;
           堆排序 :  如果内存空间允许且要求稳定性的,

           归并排序:它有一定数量的数据移动,所以我们可能过与插入排序组合,先获得一定长度的序列,然后再合并,在效率上将有所提高。

    2)  当n较大,内存空间允许,且要求稳定性 =》归并排序

    3)当n较小,可采用直接插入或直接选择排序。

        直接插入排序:当元素分布有序,直接插入排序将大大减少比较次数和移动记录的次数。

        直接选择排序 :元素分布有序,如果不要求稳定性,选择直接选择排序

    5)一般不使用或不直接使用传统的冒泡排序。

    6)基数排序
    它是一种稳定的排序算法,但有一定的局限性:
      1、关键字可分解。

      2
    、记录的关键字位数较少,如果密集更好
      3、如果是数字时,最好是无符号的,否则将增加相应的映射复杂度,可先将其正负分开排序。

     

    注明:转载请提示出处:http://blog.csdn.net/hguisu/article/details/7776068

      http://www.cnblogs.com/eniac12/p/5329396.html#s2

    展开全文
  • 算法(Algorithm),是程序设计的灵魂,它是利用系统的方法描述解决问题策略的机制。本系列文章旨在用C语言解释算法的作用,分析包括排序算法、查找算法、迭代算法、递推算法、 递归算法、枚举算法、贪心算法、回溯...
  • 快速排序】(C语言实现)

    千次阅读 多人点赞 2022-04-07 09:16:42
    快速排序算法通过多次比较和交换来实现排序,其排序流程如下: (1)首先设定一个分界值,通过该分界值将数组分成左右两部分。 (2)将大于或等于分界值的数据集中到数组右边,小于分界值的数据集中到数组的左边。此时,...
  • (1) 完成5种常用内部排序算法的演示,5种排序算法为:快速排序,直接插入排序,选择排序,堆排序,希尔排序; (2) 待排序元素为整数,排序序列存储在数据文件中,要求排序元素不少于30个; (3) 演示程序开始,...
  • 7种排序算法程序汇总

    2011-05-19 17:34:03
    7种排序算法程序汇总 冒泡排序 选择排序 插入排序 希排序尔 快速排序 二叉排序树 堆排序
  • 快速排序法:实际上是对冒泡排序法的一种改进。 算法:是描述求解问题方法的操作步骤集合。 快速排序法这一算法的基本思想是:首先设定一个分界值(一般是数组中的起始元素值),通过该分界值将数组的元素值分成左右...
  • 排序算法演示小程序

    2015-08-09 14:36:11
    简单的排序演示 有交换排序、快速排序、插入排序、堆排序、选择排序和希尔排序
  • 数据结构七大排序算法图解

    千次阅读 多人点赞 2022-04-28 09:42:58
    万字手撕七大排序(代码+动图演示) ...
  • (1)对以下6种常用的内部排序算法进行比较:起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。 (2)待排序表的表长不小于100;其中的数据要用伪随机数产生程序产生;至少要用5组不同的输入数据...
  • 算法实验课程作业,含直接插入排序,冒泡排序,归并排序,堆排序,快速排序,shell排序等
  • 数组的插入排序和快速排序

    千次阅读 2016-09-17 15:27:23
    前言 关于对数组的排序,在算法中有...而对数组排序中,插入排序和快速排序的效率要比冒泡和选择排序的效率要高,而今天就来聊一聊插入排序和快速排序的原理和实现。 插入排序 插入排序的基本操作就是将一个数据插入
  • 快速排序Java版(递归与非递归)

    千次阅读 2019-07-03 19:36:29
    快速排序(Java版) 听名字就很diao,直接上干货。(杠精别打我,支点的英文是pivot,我全拼错了) 快排一定要思路清晰,没事多写几遍,要不容易忘。 对于一个数组对它进行排序,快排的思想就是交换交换再交换,我们...
  • (1)掌握线性表的存储方式,并在此基础上实现典型的排序算法 (2)理解并掌握内部排序中几种常用算法的性能和适用场合 (3)理解并比较各种排序算法的时间复杂度和空间复杂度
  • 冒泡排序法又称为交换排序法,是从观察水中气泡变化构思而成。原理是从第一个元素开始,比较相邻元素的大小,若大小顺序有误,则对调后再进行下一个元素的比较。如此经过第一次扫描后就可以确保最后一个元素位于正确...
  • 今天就来谈谈快速排序,我们也不详谈快速排序的时间复杂度,我们重点来分析一下快速排序的思想。  快速排序的思想十分简单,假设给定一个无序的数组,我们要从小到大排列,我们只需要完成以下几步  1、选取这个...
  • 快速排序程序

    千次阅读 2007-09-24 13:28:00
    #include /*功能:快速排序start表示起始位置指针,len表示要排序的长度无返回值*/void qiuck_sort(int *start,int len){ int k;//用作记录枢轴记录关键字 int *p1,*p2,*pkey;//p1,p2分别表示高位和低位的指针,...
  • 大数据开发流程图

    千次阅读 2019-11-27 13:21:46
    1、大数据流程图 2、大数据各个环节主要技术 2.1、数据处理主要技术 Sqoop:(发音:skup)作为一款开源的离线数据传输工具,主要用于Hadoop(Hive) 与传统数据库(MySql,PostgreSQL)间的数据传递。它可以将...
  • 尝试使用python实现快速排序算法

    千次阅读 2017-02-01 22:38:44
    欢迎使用Markdown编辑器写博客本Markdown编辑器使用StackEdit修改而来,用它写博客,将会带来全新...UML序列图和流程图 离线写博客 导入导出Markdown文件 丰富的快捷键 快捷键 加粗 Ctrl + B 斜体 Ctrl + I 引用 Ctrl
  • 快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序n个项目要O(nlogn)次比较。在最坏状况下则需要O(n2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他O(nlogn)算法更快,因为它的内部...
  • qsort函数用法:作用:使用快速排序例程进行排序用法:void qsort(void *base, int nelem, int width, int (*fcmp)());程序举例:#include #include #include int sort_function( const void *a, const void *b);char ...
  • 算法笔记之快速排序

    千次阅读 2014-07-24 01:50:34
    然后对第一和第二部分递归地使用快速排序算法,直到分到最小的小组为止。 1.2 时间复杂度—— 在最差的情况下,要把n个元素的数组划分,需要n次比较和n次移动。假设用T(n) 来表示使用快速排序算法来排序n个元素
  • js流程图:aworkflow.js、aiflowjs

    万次阅读 2018-10-09 16:36:47
    用于快速构建各种关系的库 github地址:https://github.com/auto-workflow/AWorkflow 快速开始 npm install aworkflow 或者引用dist文件夹下的产出文件 访问demo npm install npm run dev 默认模版:...
  • 快速排序算法解析

    千次阅读 2013-05-02 18:08:00
    因此经常被采用,再加上快速排序思想----分治法也确实实用,因此很多软件公司的笔试面试,包括像腾讯,微软等知名IT公司都喜欢考这个,还有大大小的程序方面的考试如软考,考研中也常常出现快速排序的身影。...
  • 目录: 一:冒泡排序 定义: ...六:快速排序 定义: 实例7:迭代法 实例8:递归法 一:冒泡排序 定义: 冒泡排序(英语:Bubble Sort)是一种简单的排序算法 它重复地走访过要排序的...
  • 【算法理解】—— 快速排序(三向切分)

    千次阅读 多人点赞 2016-07-04 09:49:23
    针对于“快速排序”算法的一个介绍,并对快速排序的优化版——“快速排序(三向切分)”做一个介绍。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 61,363
精华内容 24,545
关键字:

快速排序程序流程图

友情链接: 8051f340UART.zip