算法之快速排序
快速排序:顾名思义就是排序过程比较快的排序方法(在排序过程中交换时有可能位置跳跃比较大)。
快速排序的核心思想:找数组的中值,从前往后找第一个比中值的大的数,从后往前找第一个比中值小的数,找到后将它们俩交换位置,一轮结束后,将数组分成两部分,继续进行查找。
具体步骤:
(1)先给出一个无序数组,找到他的中值,从前往后找第一个比中值的大的数,从后往前找第一个比中值小的数,找到后将它们俩交换位置;
(2)判断,若找到的这个大数位置和小数的位置都在中值处,或者大数位置在小数位置后面,则第一轮结束,将数组分为两部分;
(3)否则将找到的这两个数交换,接着给大数的位置+1,小数的位置-1;继续重复上面的步骤;
(4)当第一轮结束后,将数组按照(startIndex,highIndex-1)(lowIndex+1,endIndex)分成两部分,继续重复上面的步骤直到将数排好序;
(5)将排好序的数组打印出来。
来看一下具体的程序:
using System; using System.Collections.Generic; using System.Text; namespace prjquicksort { class Program { static void Main(string[] args) { int[] ary = new int[] { 2, 8, 6, 5, 7, 1, 9 };//先准备一个无序数组 quicksort(ary, 0, ary.Length - 1);//调用quicksort函数 foreach (int x in ary)//用foreach函数打印排好序后的数组 { Console.WriteLine(x); } } static void quicksort(int []ary, int startIndex, int endIndex)//快速排序 { //起始索引大于等于结束索引实数时,直接返回。 if (startIndex>=endIndex) { return; } //中值等于起始索引加结束索引除2位置上的值。 int middle = ary[(startIndex + endIndex) / 2]; //比中指值大的数的索引(高位索引)初始化为起始索引。 int highIndex = startIndex; //比中值小的数的索引(低位索引)初始化为结束索引。 int lowIndex = endIndex; //排序次数不确定,多次排序后数组变成有序数组。 while (true) { //在数组中从高位索引到结束索引从前往后开始找第一个大于等于中值的数。 for (int i = highIndex; i <= endIndex; i++) { //如果找到了第一个大于等于中值的数,就将这个数的索引给高位索引,并跳出循环。 if (ary[i] >= middle) { highIndex = i; break; } } //在数组中从低位索引到起始索引从后往前开始找第一个小于等于中值的数。 for (int j = lowIndex; j >= startIndex; j--) { //如果找到了第一个小于等于中值的数,就将这个数的索引给低位索引,并跳出循环。 if (ary[j] <=middle) { lowIndex = j; break; } } //如果高位索引等于低位索引,则跳出循环。 if (highIndex == lowIndex) { break; } //如果高位索引大于低位索引,则跳出循环。 if (highIndex > lowIndex) { break; } //否则将找到的两个数进行交换。 int temp = ary[highIndex]; ary[highIndex] = ary[lowIndex]; ary[lowIndex] = temp; //下一次找的时候高位索引往后挪一位,低位索引往前挪一位。 highIndex++; lowIndex--; } //将数组切成部分,第一部分从起始索引到高位索引-1;第二部分从低位索引+1到结束索引。 quicksort(ary, startIndex, highIndex - 1); quicksort(ary, lowIndex + 1, endIndex); } } }
转载于:https://blog.51cto.com/7607889/1264153