【快速排序算法-C#实现】

╰半夏微凉° 2022-09-22 15:51 170阅读 0赞

使用C\#实现快速排序算法。

快速排序的基本思想：  
分治法，即，分解，求解，组合 .  
  
分解：  
在 无序区R\[low..high\]中任选一个记录作为基准(通常选第一个记录，并记为keyValue,其下标为keyValuePosition),以此为基准划分成两个较小的 子区间R\[low,keyValuePosition- 1\]和R\[keyValuePosition+ 1 , high\],并使左边子区间的所有记录均小于等于基准记录,右边子区间的所有记录均大于等于基准记录,基准记录无需参加后续的排序。而划分的关键是要求出 基准记录所在的位置keyValuePosition.  
  
求解：  
通过递归调用快速排序对左、右子区间R\[low..keyValuePosition-1\]和R\[keyValuePosition+1..high\]快速排序  
  
组合：  
当"求解"步骤中的两个递归调用结束时，其左、右两个子区间已有序。对快速排序而言，"组合"步骤无须做什么，可看作是空操作。  
  
具体过程：  
设序列为R\[low,high\]，从其中选第一个为基准，设为keyValue,然后设两个指针i和j,分别指向序列R\[low,high\]的起始和结束位置上：  
1），将i逐渐增大，直到找到大于keyValue的关键字为止；  
2），将j逐渐减少，直到找到小于等于keyValue的关键字为止；  
3），如果i<j，即R\[i,j\]的元素数大于1，则交换R\[i\]和R\[j\]；  
4），将基准记录keyValue放到合适的位置上，即i和j同时指向的位置（或者同时指向的位置-1）,则此位置为新的keyValuePosition。

class Program
        {
            static void Main(string[] args)
            {
                Stopwatch watch = new Stopwatch();
                int[] myArray = new int[] { 12,3,4,24,274,201,0,2,45};
    
                int lowindex = 0;//数组的起始位置
                int hightindex = myArray.Length - 1;//数组的终止位置
    
                watch.Start();
                QuickSortFunction(myArray, lowindex, hightindex);
                Console.WriteLine("时间=" + watch.ElapsedMilliseconds.ToString()+"毫秒");
    
                //输出排完之后的数组
                for (int i = 0; i < myArray.Length; i++)
                {
                    Console.WriteLine(myArray[i].ToString());
                }
            }
    
            快速排序（目标数组，数组的起始位置，数组的终止位置）
            private static void QuickSortFunction(int [] array,int low,int high)
            {
                try
                {
                    //当传递的目标数组含有两个以上的元素时，进行递归调用。（即：当传递的目标数组只含有一个元素时，此趟排序结束）
                    if (low < high)
                    {
                        int keyValuePosition = KeyValuesPositionFuntion(array, low, high);
                        QuickSortFunction(array, low, keyValuePosition - 1);
                        QuickSortFunction(array, keyValuePosition + 1, high);
                    }
                }
                catch (Exception ex)
                {
                    Console.WriteLine(ex.Message);
                }
            }
    
            //快速排序的核心部分：确定关键值在数组中的位置，以此将数组划分成左右两区间，关键值游离在外。（返回关键值应在数组中的下标）
            private static int KeyValuesPositionFuntion(int[] array, int low, int high)
            {
                int leftindex = low;
                int reightindex = high;
                int keyvalue = array[low];//数组的第一个元素作为关机值
                int temp;
    
                //当 （左侧动态下标 == 右侧动态下标） 时跳出循环
                while (leftindex<reightindex)
                {
                    //左侧动态下标逐渐增加，直至找到大于keyValue的下标
                    while (leftindex<reightindex&&array[leftindex]<=keyvalue) 
                    {
                        leftindex++;
                    }
                    右侧动态下标逐渐减小，直至找到小于或等于keyValue的下标
                    while (leftindex<reightindex&&array[reightindex]>keyvalue) 
                    {
                        reightindex--;
                    }
                    if (leftindex < reightindex) 
                    {
                        //如果leftIndex < rightIndex，则交换左右动态下标所指定的值；当leftIndex==rightIndex时，跳出整个循环
                        temp = array[leftindex];
                        array[leftindex] = array[reightindex];
                        array[reightindex] = temp;
                    }
                }
    
                //当左右两个动态下标相等时（即：左右下标指向同一个位置），此时便可以确定keyValue的准确位置
                temp = keyvalue;
                if (temp < array[reightindex])  
                {
                    //当keyValue < 左右下标同时指向的值，将keyValue与rightIndex - 1指向的值交换，并返回rightIndex - 1
                    array[low] = array[reightindex - 1];
                    array[reightindex - 1] = temp;
                    return reightindex - 1;
                }
                else 
                {
                    //当keyValue >= 左右下标同时指向的值，将keyValue与rightIndex指向的值交换，并返回rightIndex
                    array[low] = array[reightindex];
                    array[reightindex] = temp;
                    return reightindex;
                }
            }
        }

原文地址：http://www.cnblogs.com/mingmingruyuedlut/archive/2011/08/17/2143062.html