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-完成的時候，此時令循環結束）。 例子：

以一個數組作為示例，取區間第一個數為基准數。

 

0

1

2

3

4

5

6

7

8

9

72

6

57

88

60

42

83

73

48

85

初始時，i = 0;  j = 9;   X = a[i] = 72

由於已經將a[0]中的數保存到X中，可以理解成在數組a[0]上挖了個坑，可以將其它數據填充到這來。

從j開始向前找一個比X小或等於X的數。當j=8，符合條件，將a[8]挖出再填到上一個坑a[0]中。a[0]=a[8]; i++;  這樣一個坑a[0]就被搞定了，但又形成了一個新坑a[8]，這怎麼辦了？簡單，再找數字來填a[8]這個坑。這次從i開始向後找一個大於X的數，當i=3，符合條件，將a[3]挖出再填到上一個坑中a[8]=a[3]; j--; 

數組變為：

0

1

2

3

4

5

6

7

8

9

48

6

57

88

60

42

83

73

88

85

 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]。

數組變為：

0

1

2

3

4

5

6

7

8

9

48

6

57

42

60

72

83

73

88

85

可以看出a[5]前面的數字都小於它，a[5]後面的數字都大於它。因此再對a[0…4]和a[6…9]這二個子區間重復上述步驟就可以了。