C#之快速排序

算法描述

1.假定数组首位元素为“枢轴”，设定数列首位（begin）与末位（end）索引；

2.由末位索引对应元素与“枢轴”进行比较，如果末位索引对应元素大于“枢轴”元素，对末位索引减一（end--），直到比较出大于“枢轴”元素，将该元素覆盖到首位，对应索引上的数值空出；

3.由首位索引对应元素与“枢轴”进行比较，如果首位索引对应元素小于“枢轴”元素，对首位索引加一（begin++）;直到比较出小于“枢轴”元素，将该元素覆盖到步骤2中空出位置，同时对应索引上的数值空出；

4.重复步骤2与步骤3，直到begin==end结束循环，这时候begin与end已指向同一位置，将“枢轴”元素覆盖到该位置；

5.这时候该位置前面元素都小于“枢轴”元素，该位置后面元素都大于“枢轴”元素，第一轮循环结束，对前后两部分执行相同步骤，通过“递归”最终将数组中数值完成排序；

代码实现

 public int[] Quick(int[] arr, int begin, int end) // 通过自我调用实现“递归”  

{

 if (begin >= end)
            { 

 return arr;
            } 

 int pivotIndex = QuickCondition(arr, begin, end); // 获得“枢轴”索引  

 Quick(arr, begin, pivotIndex - 1); // 对所有小于“枢轴”元素再次比较 

            Quick(arr, pivotIndex + 1, end);// 对所有大于“枢轴”元素再次比较 

 return arr;
        } 

 public int QuickCondition(int[] arr, int begin, int end)
        { 

 int pivot = arr[begin]; // 设定首位为“枢轴”元素 

 while (begin < end)
            { 

 while (arr[end] > pivot && begin < end) // 通过比较找到小于“枢轴”元素的索引，进行替换  

 {
                    end--;
                }

                arr[begin] = arr[end]; 

 while (arr[begin] < pivot && begin < end) // 通过比较找到第大于“枢轴”元素的索引，进行替换 

 {
                    begin++;
                }

                arr[end] = arr[begin];
            }
            arr[begin] = pivot; // 当begin == end 跳出循环将“枢轴”覆盖到该索引上 

 return begin;
        }

完整代码

using System; 

namespace QuickSortApplication
{ 

 class Program
    { 

 static void Main(string[] args)
        { 

 var setArray = new SetArray(); 

 var quickSort = new QuickSort(); 

 int[] arr = setArray.GetArray(); 

 int[] array = quickSort.Quick(arr, 0, arr.Length - 1);
            quickSort.DisPlay(array);
            
            Console.ReadLine();
        }
    } 

 class SetArray
    { 

 public int[] GetArray()
        { 

 int length; 

 int[] arr;

            Console.WriteLine("请输入数组长度：");
            length = Convert.ToInt32(Console.ReadLine());

            arr = new int[length]; for (int i = 0; i <= length - 1; i++)
            {
                Console.Write("请输入数组第{0}位数值：", i);
                arr[i] = Convert.ToInt32(Console.ReadLine());
            }

            Console.Clear();

            Console.Write("arr[] = {"); foreach (int item in arr)
            {
                Console.Write(item + " ");
            }
            Console.Write("}\n"); return arr;
        }
    } 

 class QuickSort
    { 

 public int[] Quick(int[] arr, int begin, int end) // 通过自我调用实现“递归”  

 { 

 if (begin >= end)
            {

 return arr;
            } 

 int pivotIndex = QuickCondition(arr, begin, end); // 获得“枢轴”索引  

 Quick(arr, begin, pivotIndex - 1); // 对所有小于“枢轴”元素再次比较 

             Quick(arr, pivotIndex + 1, end);// 对所有大于“枢轴”元素再次比较

            return arr;
        } 

 public int QuickCondition(int[] arr, int begin, int end)
        { 

 int pivot = arr[begin]; // 设定首位为“枢轴”元素 

 while (begin < end)
            { 

 while (arr[end] > pivot && begin < end) // 通过比较找到小于“枢轴”元素的索引，进行替换  

 {
                    end--;
                }

                arr[begin] = arr[end]; 

 while (arr[begin] < pivot && begin < end) // 通过比较找到第大于“枢轴”元素的索引，进行替换  

 {
                    begin++;
                }

                arr[end] = arr[begin];
            }
            arr[begin] = pivot; // 当begin == end 跳出循环将“枢轴”覆盖到该索引上

          return begin;
        } 

 public void DisPlay(int[] arr)
        {
            Console.Write("快速排序："); foreach (int item in arr)
            {
                Console.Write(item + " ");
            }
            Console.WriteLine();
        }
    }
}