【C#】3.算法温故而知新 - 快速排序-阿里云开发者社区

开发者社区> 人工智能> 正文

【C#】3.算法温故而知新 - 快速排序

简介:

快速排序相比冒泡排序,每次交换是跳跃式的。每次排序的时候设置一个基准点,将小于等于基准点的数全部放到基准点的左边,将大于等于基准点的数放到基准点的右边。这样每次交换的时候就不会像冒泡排序一样只能在相邻的数之间进行交换,交换的距离就大得多了。因此总的比较和交换次数就少了,速度自然就提高了。

当在最坏的情况下,仍可能是相邻的两个数进行交换,因此快速排序的最差时间复杂度和冒泡排序一样,都是O(N²),它的平均时间复杂度为O(N㏒N)。

 

示例图片如下

 

 

 

代码:

复制代码
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    public class Program
    {
        private static int[] a = new int[10] { 6, 1, 2, 7, 9, 3, 4, 5, 10, 8 };//初始化一个数组,其中有10个数,这里假定是我们输入的数,需要从小到大排序
        public static void Main(string[] args)
        {
            QuickSort(0, a.Length - 1);//最左边数和最右边数的下标
            //输出排序后的结果
            for (int i = 0; i < a.Length; i++)
                Console.Write("  " + a[i]);
        }

        /// <summary>交换方法 </summary>
        /// <param name="left">最左边数的下标</param>
        /// <param name="right">最右边数的下标</param>
        private static void QuickSort(int left, int right)
        {
            int i, j, t, temp;
            if (left > right)//下标交错即返回
                return;
            temp = a[left];//temp中存的就是基准数,假定最左边的数为基准数
            i = left;//左边数的下标
            j = right;//右边数的下标

            while (i != j)//当下标不相等时,直到i=j时停止
            {
                //顺序很重要,要先从右往左找
                while (a[j] >= temp && i < j)//找到大于基准数的数
                    j--;
                //再从从左往右找
                while (a[i] <= temp && i < j)//找到小于基准数的数
                    i++;

                //交换两个数在数组中的位置
                if (i < j)
                {
                    t = a[i];
                    a[i] = a[j];
                    a[j] = t;
                }
            }
            //最终将基准数归位
            a[left] = a[i];
            a[i] = temp;

            QuickSort(left, i - 1);//继续处理左边的,这里是一个递归的过程
            QuickSort(i + 1, right);//继续处理右边的,这里是一个递归的过程
        }

    }
}
复制代码





本文转自叶超Luka博客园博客,原文链接:http://www.cnblogs.com/yc-755909659/p/3988414.html,如需转载请自行联系原作者

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章