C#之快速排序

发布时间:2018/4/13 16:40:46 次浏览

算法描述

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();
        }
    }
}
复制代码