快捷導(dǎo)航

c# 快速排序算法

更新時(shí)間：2013年10月23日 22:08:42 作者：

快速排序使用分治法（Divide and conquer）策略來(lái)把一個(gè)串行（list）分為兩個(gè)子串行（sub-lists）

快速排序使用分治法（Divide and conquer）策略來(lái)把一個(gè)串行（list）分為兩個(gè)子串行（sub-lists）。

步驟為：

1.從數(shù)列中挑出一個(gè)元素，稱為 "基準(zhǔn)"（pivot），

2.重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）。在這個(gè)分區(qū)退出之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱為分區(qū)（partition）操作。

3.遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。

遞歸的最底部情形，是數(shù)列的大小是零或一，也就是永遠(yuǎn)都已經(jīng)被排序好了。雖然一直遞歸下去，但是這個(gè)算法總會(huì)退出，因?yàn)樵诿看蔚牡╥teration）中，它至少會(huì)把一個(gè)元素?cái)[到它最后的位置去。

平均時(shí)間復(fù)雜度	$\Theta(n\log n)$

快速排序通常明顯比其他Ο(n log n) 算法更快

快速排序

復(fù)制代碼代碼如下:

public static void Sort(int[] numbers) 
{ 
    QuickSort(numbers, 0, numbers.Length - 1); 
} 
private static void QuickSort(int[] numbers, int left, int right) 
{ 
    if (left < right) 
    { 
        int middle = numbers[(left + right) / 2]; 
        int i = left - 1; 
        int j = right + 1; 
        while (true) 
        { 
            while (numbers[++i] < middle) ; 

            while (numbers[--j] > middle) ; 

            if (i >= j) 
                break; 

            Swap(numbers, i, j); 
        } 

        QuickSort(numbers, left, i - 1); 
        QuickSort(numbers, j + 1, right); 
    } 
} 

private static void Swap(int[] numbers, int i, int j) 
{ 
    int number = numbers[i]; 
    numbers[i] = numbers[j]; 
    numbers[j] = number; 
}

調(diào)用：

復(fù)制代碼代碼如下:

int[] y = new int[] {4,8,2222,2,1,121,13,434,56,1111,65,7,8 }; 
Sort(y); 
foreach (var item in y) 
{ 
    Console.WriteLine(item); 
} // 1 2 4 7 8 8 13 56 65 121 434 1111 2222

您可能感興趣的文章: