首页  >  文章  >  后端开发  >  C# 快速排序

C# 快速排序

黄舟
黄舟原创
2017-02-09 16:15:192096浏览

C# 快速排序

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Sort
{
    class QuickSorter
    {
        private static int[] myArray;
        private static int arraySize;
        public static int[] Sort(int[] a)
        {
            arraySize = a.Length;
            QuickSort(a, 0,arraySize- 1);
	    return a;
        }
        private static void QuickSort(int[] myArray, int left, int right)
        {
            int i, j, s;
            if (left < right)
            {
                i = left - 1;
                j = right + 1;
                s = myArray[(i + j) / 2];
                while (true)
                {
                    while (myArray[++i] < s) ;
                    while (myArray[--j] > s) ;
                    if (i >= j)
                        break;
                    Swap(ref myArray[i], ref myArray[j]);
                }
                QuickSort(myArray, left, i - 1);
                QuickSort(myArray, j + 1, right);
            }
        }
        private static void Swap(ref int left, ref int right)
        {
            int temp;
            temp = left;
            left = right;
            right = temp;
        }
    }
}

快速排序的思想:

设要排序的数组是A[0]……A[N-1],首先任意选取一个数据(通常选用数组的第一个数)作为关键数据,然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一趟快速排序。值得注意的是,快速排序不是一种稳定的排序算法,也就是说,多个相同的值的相对位置也许会在算法结束时产生变动。

一趟快速排序的算法是:

1)设置两个变量i、j,排序开始的时候:i=0,j=N-1;

2)以第一个数组元素作为关键数据,赋值给key,即key=A[0];

3)从j开始向前搜索,即由后开始向前搜索(j--),找到第一个小于key的值A[j],将值为key的项与A[j]交换;

4)从i开始向后搜索,即由前开始向后搜索(i++),找到第一个大于key的A[i],将值为key的项与A[i]交换;

5)重复第3步

6)重复第3、4、5步,直到i=j; (3,4步中,没找到符合条件的值,即3中A[j]不小于key,4中A[j]不大于key的时候改变j、i的值,使得j=j-1,i=i+1,直至找到为止。找到符合条件的值,进行交换的时候i, j指针位置不变。另外,i==j这一过程一定正好是i+或j-完成的时候,此时令循环结束)。

例子:

以一个数组作为示例,取区间第一个数为基准数。

1053.png

 i = 3;   j = 7;   X=72

再重复上面的步骤,先从后向前找,再从前向后找。

从j开始向前找,当j=5,符合条件,将a[5]挖出填到上一个坑中,a[3] = a[5]; i++;

从i开始向后找,当i=5时,由于i==j退出。

此时,i = j = 5,而a[5]刚好又是上次挖的坑,因此将X填入a[5]。

数组变为:

1054.png

以上就是C# 快速排序的内容,更多相关内容请关注PHP中文网(www.php.cn)!


声明:
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
上一篇:C# 选择排序下一篇: C# 归并排序