• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

C#快速排序详解

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

 

使用快速排序法对一列数字进行排序的过程

 

 

快速排序使用分治法(Divide and conquer)策略来把一个序列(list)分为两个子序列(sub-lists)。

步骤为:

  1. 从数列中挑出一个元素,称为 "基准"(pivot),
  2. 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆放在基准的后面(相同的数可以到任一边)。在这个分割结束之后,该基准就处于数列的中间位置。这个称为分割(partition)操作。
  3. 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递归下去,但是这个演算法总会结束,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。

C#算法实现

 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace 快速排序    //***对相同元素, 不稳定的排序算法***
{
    //相对来说,快速排序数值越大速度越快 。  快速排序是所有排序里面最快的

    class Program
    {
        static void Main(string[] args)
        {
            int[] arr = { 15, 22, 35, 9, 16, 33, 15, 23, 68, 1, 33, 25, 14 }; //待排序数组
            QuickSort(arr, 0, arr.Length - 1);  //调用快速排序函数。传值(要排序数组,基准值位置,数组长度)

            //控制台遍历输出
            Console.WriteLine("排序后的数列:");
            foreach (int item in arr)
                Console.WriteLine(item);
        }

        private static void QuickSort(int[] arr, int begin, int end)
        {
            if (begin >= end) return;   //两个指针重合就返回,结束调用
            int pivotIndex = QuickSort_Once(arr, begin, end);  //会得到一个基准值下标

            QuickSort(arr, begin, pivotIndex - 1);  //对基准的左端进行排序  递归
            QuickSort(arr, pivotIndex + 1, end);   //对基准的右端进行排序  递归
        }

        private static int QuickSort_Once(int[] arr, int begin, int end)
        {
            int pivot = arr[begin];   //将首元素作为基准
            int i = begin;
            int j = end;
            while (i < j)
            {
                //从右到左,寻找第一个小于基准pivot的元素
                while (arr[j] >= pivot && i < j) j--; //指针向前移
                arr[i] = arr[j];  //执行到此,j已指向从右端起第一个小于基准pivot的元素,执行替换

                //从左到右,寻找首个大于基准pivot的元素
                while (arr[i] <= pivot && i < j) i++; //指针向后移
                arr[j] = arr[i];  //执行到此,i已指向从左端起首个大于基准pivot的元素,执行替换
            }

            //退出while循环,执行至此,必定是 i= j的情况(最后两个指针会碰头)
            //i(或j)所指向的既是基准位置,定位该趟的基准并将该基准位置返回
            arr[i] = pivot;
            return i;
        }

    }
}

 

http://www.cnblogs.com/weiios/p/3933994.html


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
[C#技术参考]在PictureBox中绘图防止闪烁的办法发布时间:2022-07-14
下一篇:
c#可以有多个Main()函数发布时间:2022-07-14
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap