读书笔记算法导论快速排序 QuickSort 使用最后一个元素作为pivot

时间：2011-04-05 来源：听说读写

快速排序是实际编程应用中最常见的排序方式

他有非常好的性能

最差情况的时间复杂度为 O(N平方)

平均情况的时间复杂度为 O(N logN) ,而且拥有一个非常小的系数

并且空间复杂度也非常小就是O(N)

不过这个算法也是比较难理解的...

以下是一个使用最后一个元素作为pivot的快速算法实现

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

namespace IntroduceToAlgorithm
{

    public class QuickSort
    {
        public void Sort(int[] A, int StartIndex = 1, int EndIndex = -1)
        {
            if (EndIndex == -1)
            {
                EndIndex = A.Length;
            }
            if (StartIndex < EndIndex)
            {
                int q = Partition(A, StartIndex, EndIndex);
                 
                Sort(A, StartIndex, q - 1);
                Sort(A, q + 1, EndIndex);
            }
        }

        public int Partition(int[] A, int StartIndex, int EndIndex)
        {
            int x = A[EndIndex - 1];
            int i = StartIndex - 1;

            for (int j = StartIndex; j <= EndIndex - 1; j++)
            {
                if (A[j - 1] <= x)
                {
                    i = i + 1;
                    Exchange(A, i - 1, j - 1);
                }
                //A.Print();
            } 
            Exchange(A, i, EndIndex - 1);
            //A.Print();
            return i + 1;


        }

        public void Exchange(int[] A, int i, int i2)
        {
            int val = A[i];
            A[i] = A[i2];
            A[i2] = val;
        }
    }

}