欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

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

相關(guān)文章

最新評(píng)論