Dowemo
0 0 0 0

Three fast sorting algorithms for and optimization ofreadingcomment ( 0 )..Category: R & d ( 46 )

One one. Basic idea of fast sorting

The idea of fast sorting uses the idea of conquer, dividing the sorted columns into two parts by the sort, and the keywords recorded are smaller than those recorded. After that, the two parts of the record are sorted to achieve the whole sequence order.

Two second. Three steps for quick sorting

1 ) select base: in the columns to be sorted, pick an element in a way, as"baseline"( pivot );

2 ) division operation: the actual position of this datum in the sequence, dividing the sequence into two subsequence columns. At this point, the elements on the left side of the baseline are smaller than the benchmark, and the elements on the right side of the baseline are larger than the base

3 ) a fast sorting of two sequences, until the order column is empty or only one element;

Three three. How to select a baseline element

For the divide and conquer algorithm, when each partition, the algorithm can be divided into two columns, then the efficiency will be maximum. In other words, the selection is important. Choosing the benchmark determines the length of two columns, and then the efficiency of the whole algorithm is determined by the method.

The most ideal method is that the selected datum can be divided into two sequences with equal length and length.

Method: fixed baseline element ( basic quick sort )

Idea: the first or last element of the sequence column as a reference element.

///<summary>
///1.0 固定基准元(基本的快速排序)
///</summary>
 public static void QsortCommon(int[] arr, int low, int high)
 {
 if (low> = high) return;//递归出口
 int partition = Partition(arr, low, high);//将> = x 的元素交换到右边区域,将 <= x 的元素交换到左边区域
 QsortCommon(arr, low, partition - 1);
 QsortCommon(arr, partition + 1, high);
 }
///<summary>
///固定基准元,默认数组第一个数为基准元,左右分组,返回基准元的下标
///</summary>
 public static int Partition(int[] arr, int low, int high)
 {
 int first = low;
 int last = high;
 int key = arr[low];//取第一个元素作为基准元
 while (first <last)
 {
 while (first <last && arr[last]> = key)
 last--;
 arr[first] = arr[last];
 while (first <last && arr[first] <= key)
 first++;
 arr[last] = arr[first];
 }
 arr[first] = key;//基准元居中
 return first;
 }

Note: basic quick sorting selects the first or last element as a baseline. But it's a very bad way to handle it.

Test data:

Test data analysis: if the input sequence is random, processing time can be accepted. If the array is ordered, the split is a very bad partition. Because each partition can only make the sequence to be ordered, the worst case is the worst case, and the time complexity is ( n^2 ). Moreover, the data entered is an ordered or ordered situation that's quite common. Therefore, using the first element as a reference element is very bad, and in order to avoid this situation, the following two methods to get the benchmark.

Method: random datum element

Idea: to take any element in the sorted column as a reference element.

The cause of the introduction: when the column is ordered, the fixed base element is used to reduce the efficiency. To alleviate this, the random selection.

///<summary>
///2.0 随机基准元
///</summary>
 public static void QsortRandom(int[] arr, int low, int high)
 {
 if (low> = high) return;//递归出口
 PartitionRandom(arr, low, high);//随机基准元
 int partition = Partition(arr, low, high);//将> = x 的元素交换到右边区域,将 <= x 的元素交换到左边区域
 QsortRandom(arr, low, partition - 1);
 QsortRandom(arr, partition + 1, high);
 }
///<summary>
///随机基准元,将确定好的基准元与第一个数交换,无返回值
///</summary> 
 public static void PartitionRandom(int[] arr, int low, int high)
 {
 Random rd = new Random();
 int randomIndex = rd.Next() % (high - low) + low;//取数组中随机下标
 Swap(arr, randomIndex, low);//与第一个数交换
 }

Test data:

Test data analysis:: this is a relatively secure policy. Because the location of the base element is random, the resulting segmentation won't always appear to be poor. It's still the worst case when the entire array number is equal, and the time complexity is o ( n^2 ). In fact, randomization fast sorting gets the worst probability of theory for 1 ( 2^n ). So randomization fast sorting can achieve the desired time complexity for most input data. A predecessor made a summary: "randomization quick sorting can meet the character needs of a person 's lifetime.". "

Method three: three data extraction methods

Because of the random selection, we can reduce the probability of bad segmentation, but still be the worst condition or the n^2 ( ), which can be used to.

Analysis: the best division is to divide the sequence of the sequence to be ordered, the best state we can use the middle value of the sequence, as well as the n. But it's hard to calculate, and it'll significantly slow down the speed. The estimation of this value can be obtained by randomly selecting three elements and using their median as reference. In fact, there's no much help in randomness, so the general practice is to use the values of the values of three elements at the left, right, and center. It's obvious that the median segmentation method eliminates the bad situation of input, and reduces the count of approximately 14 %.

Example: to sort order colum &: 8 1 4 9 6 3 5 2 7 0

Left is: 8, 0 on the right,

After we take three numbers, the middle number is the pivot, the pivot is 6.

Note: when selecting the central axis value, you can select from the left to five elements or more elements, general, with ( 2 t + 1 ) mean area method ( median-of- ), median.

Specific ideas: to sort the data from low, mid, high in the sort sequence, take the data in their middle as a baseline, and store the datum with 0 subscript elements.

use three, use 0 subscript elements to store reference.

///<summary>
///3.0 三数取中
///</summary>
 public static void QsortMedianOfThree(int[] arr, int low, int high)
 {
 if (low> = high) return;//递归出口
 PartitionMedianOfThree(arr, low, high);//三数取中
 int partition = Partition(arr, low, high);//将> = x 的元素交换到右边区域,将 <= x 的元素交换到左边区域
 QsortMedianOfThree(arr, low, partition - 1);
 QsortMedianOfThree(arr, partition + 1, high);
 }
///<summary>
///三数取中确定基准元,将确定好的基准元与第一个数交换,无返回值
///</summary> 
 public static void PartitionMedianOfThree(int[] arr, int low, int high)
 {
 int mid = low + (high + -low)/2;
 if (arr[mid]> arr[high])
 {
 Swap(arr, mid, high);
 }
 if (arr[low]> arr[high])
 {
 Swap(arr, low, high);
 }
 if (arr[mid]> arr[low])
 {
 Swap(arr, mid, low);
 }//将中间大小的数与第一个数交换
 }

Test data:

Test data analysis: use In three numbers. The advantage is obvious, but it doesn't handle repeating arrays.

Four four. Two optimization methods

Optimization: when the length of the sorted sequence is divided into a certain size, the sequence.

Cause: for a small and partially ordered array, you can quickly row rows. When the length of the sequence is divided into a certain size, the efficiency of the segmentation is less than that of the insertion sequence, which can be used I.

Due range: sequence length n = 10, although any cutoff range between 5 ~ 20 can produce similar results, this approach avoids some harmful degradation scenarios.

From the data structure and analysis, mark allen, weiness.

///<summary>
///4.0 三数取中+插排
///</summary> 
 public static void QsortThreeInsert(int[] arr, int low, int high)
 {
 if (high - low + 1 <10)
 {
 InsertSort(arr, low, high);
 return;
 }//插排,递归出口
 PartitionMedianOfThree(arr, low, high);//三数取中
 int partition = Partition(arr, low, high);//将> = x 的元素交换到右边区域,将 <= x 的元素交换到左边区域
 QsortMedianOfThree(arr, low, partition - 1);
 QsortMedianOfThree(arr, partition + 1, high);
 }

Test data:

Test data analysis: use for random numbe & Select baseline + insert in three numbers. Efficiency can also be improved, which is really useful for sorted arrays, without any use. Because the sequence is already ordered, each partition can only make the sequence of the sequence. At this point, the can't play. So there's no time to do this. In addition, the selection of reference + interpolation or can't be processed.

Optimization 2: after the end of the segment, you can sum the elements that are equal to key, and continue to divide the next segment without further segmentation.

Example:

To sort sequence 1 4 6 7 6 HSPA 7 8

Select a baseline in the: Number 6 of subscript 4

After conve & ion, the sequence to be split: 6 4 6 7 1 6 7 6 8 6

Baseline key: 6

After this division, the result isn't equal to the result of the key element. 1 4 6 6 7 6 7 6 8 6

The next two subsequence colum &: 1 4 6, and 7 6 lpt 6

After this division, the result of equal processing to the key element: 1 4 6 6 6 6 6 7 8 7

The next two subsequence colum &: 1 4 and 7 8 7

After comparison, we can see that after division, the elements that are equal to key can reduce the number of iterations, and improve the efficiency.

Specific procedures: in processing, there are two steps

The first step, in the division process, put the key equality element into the end of the array

Second, after the division ends, move the element with key equal to the pivot.

///<summary>
///5.0 三数取中+插排+聚集相同元素
///</summary> 
 public static void QsortThreeInsertGather(int[] arr, int low, int high)
 {
 if (high - low + 1 <10)
 {
 InsertSort(arr, low, high);
 return;
 }//插排,递归出口
 PartitionMedianOfThree(arr, low, high);//三数取中
//进行左右分组(处理相等元素)
 int first = low;
 int last = high;
 int left = low;
 int right = high;
 int leftLength = 0;
 int rightLength = 0;
 int key = arr[first];
 while (first <last)
 {
 while (first <last && arr[last]> = key)
 {
 if (arr[last] == key)//处理相等元素,将相等的元素放置数组两端
 {
 Swap(arr, last, right);
 right--;
 rightLength++;
 }
 last--;
 }
 arr[first] = arr[last];
 while (first <last && arr[first] <= key)
 {
 if (arr[first] == key)
 {
 Swap(arr, first, left);
 left++;
 leftLength++;
 }
 first++;
 }
 arr[last] = arr[first];
 }
 arr[first] = key;
//一次快排结束
//把与基准元key相同的元素移到最终位置周围
 int i = first - 1;
 int j = low;
 while (j <left && arr[i]!= key)
 {
 Swap(arr, i, j);
 i--;
 j++;
 }
 i = last + 1;
 j = high;
 while (j> right && arr[i]!= key)
 {
 Swap(arr, i, j);
 i++;
 j--;
 }
 QsortThreeInsertGather(arr, low, first - leftLength - 1);
 QsortThreeInsertGather(arr, first + rightLength + 1, high);
 }

Test data:

Test data analysis: + interpolation + aggregation of equal elements, the effect is good.

Cause: in an array, if there are equal elements, you can reduce the number of redundant partitions. This is especially apparent in repeating arrays.

In fact, the isn't a big one.

The following is the full test source:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Diagnostics;
using System.Threading;
namespace Sort
{
 class Program
 {
 static void Main(string[] args)
 {
//开启10M的堆栈空间的线程
 ThreadStart ts = new ThreadStart(Sort.DoQsort);
 Thread thread = new Thread(ts, 10000000);
 thread.Start();
 }
 }
 class Sort
 {
 public static void DoQsort()
 {
 int[] arr = new int[100000];//10W个空间大小的数组
//Random rd = new Random();
//for (int i = 0; i <arr.Length; i++)//随机数组
//{
//arr[i] = rd.Next();
//}
//for (int i = 0; i <arr.Length; i++)//升序数组
//{
//arr[i] = i;
//}
//for (int i = 0; i <arr.Length; i++)//降序数组
//{
//arr[i] = arr.Length - 1 - i;
//}
 for (int i = 0; i <arr.Length; i++)//重复数组
 {
 arr[i] = 5768461;
 }
 Stopwatch watch = new Stopwatch();
 watch.Start();//开始计时
//QsortCommon(arr, 0, arr.Length - 1);//固定基准元
//QsortRandom(arr, 0, arr.Length - 1);//随机基准元
//QsortMedianOfThree(arr, 0, arr.Length - 1);//三数取中
//QsortThreeInsert(arr, 0, arr.Length - 1);//三数取中+插排
 QsortThreeInsertGather(arr, 0, arr.Length - 1);//三数取中+插排+聚集相同元素
 watch.Stop();//计时结束
 Console.WriteLine(watch.ElapsedMilliseconds.ToString());
 }
///<summary>
///1.0 固定基准元(基本的快速排序)
///</summary>
 public static void QsortCommon(int[] arr, int low, int high)
 {
 if (low> = high) return;//递归出口
 int partition = Partition(arr, low, high);//将> = x 的元素交换到右边区域,将 <= x 的元素交换到左边区域
 QsortCommon(arr, low, partition - 1);
 QsortCommon(arr, partition + 1, high);
 }
///<summary>
///2.0 随机基准元
///</summary>
 public static void QsortRandom(int[] arr, int low, int high)
 {
 if (low> = high) return;//递归出口
 PartitionRandom(arr, low, high);//随机基准元
 int partition = Partition(arr, low, high);//将> = x 的元素交换到右边区域,将 <= x 的元素交换到左边区域
 QsortRandom(arr, low, partition - 1);
 QsortRandom(arr, partition + 1, high);
 }
///<summary>
///3.0 三数取中
///</summary>
 public static void QsortMedianOfThree(int[] arr, int low, int high)
 {
 if (low> = high) return;//递归出口
 PartitionMedianOfThree(arr, low, high);//三数取中
 int partition = Partition(arr, low, high);//将> = x 的元素交换到右边区域,将 <= x 的元素交换到左边区域
 QsortMedianOfThree(arr, low, partition - 1);
 QsortMedianOfThree(arr, partition + 1, high);
 }
///<summary>
///4.0 三数取中+插排
///</summary> 
 public static void QsortThreeInsert(int[] arr, int low, int high)
 {
 if (high - low + 1 <10)
 {
 InsertSort(arr, low, high);
 return;
 }//插排,递归出口
 PartitionMedianOfThree(arr, low, high);//三数取中
 int partition = Partition(arr, low, high);//将> = x 的元素交换到右边区域,将 <= x 的元素交换到左边区域
 QsortMedianOfThree(arr, low, partition - 1);
 QsortMedianOfThree(arr, partition + 1, high);
 }
///<summary>
///5.0 三数取中+插排+聚集相同元素
///</summary> 
 public static void QsortThreeInsertGather(int[] arr, int low, int high)
 {
 if (high - low + 1 <10)
 {
 InsertSort(arr, low, high);
 return;
 }//插排,递归出口
 PartitionMedianOfThree(arr, low, high);//三数取中
//进行左右分组(处理相等元素)
 int first = low;
 int last = high;
 int left = low;
 int right = high;
 int leftLength = 0;
 int rightLength = 0;
 int key = arr[first];
 while (first <last)
 {
 while (first <last && arr[last]> = key)
 {
 if (arr[last] == key)//处理相等元素
 {
 Swap(arr, last, right);
 right--;
 rightLength++;
 }
 last--;
 }
 arr[first] = arr[last];
 while (first <last && arr[first] <= key)
 {
 if (arr[first] == key)
 {
 Swap(arr, first, left);
 left++;
 leftLength++;
 }
 first++;
 }
 arr[last] = arr[first];
 }
 arr[first] = key;
//一次快排结束
//把与基准元key相同的元素移到最终位置周围
 int i = first - 1;
 int j = low;
 while (j <left && arr[i]!= key)
 {
 Swap(arr, i, j);
 i--;
 j++;
 }
 i = last + 1;
 j = high;
 while (j> right && arr[i]!= key)
 {
 Swap(arr, i, j);
 i++;
 j--;
 }
 QsortThreeInsertGather(arr, low, first - leftLength - 1);
 QsortThreeInsertGather(arr, first + rightLength + 1, high);
 }
///<summary>
///固定基准元,默认数组第一个数为基准元,左右分组,返回基准元的下标
///</summary>
 public static int Partition(int[] arr, int low, int high)
 {
 int first = low;
 int last = high;
 int key = arr[low];//取第一个元素作为基准元
 while (first <last)
 {
 while (first <last && arr[last]> = key)
 last--;
 arr[first] = arr[last];
 while (first <last && arr[first] <= key)
 first++;
 arr[last] = arr[first];
 }
 arr[first] = key;//基准元居中
 return first;
 }
///<summary>
///随机基准元,将确定好的基准元与第一个数交换,无返回值
///</summary> 
 public static void PartitionRandom(int[] arr, int low, int high)
 {
 Random rd = new Random();
 int randomIndex = rd.Next() % (high - low) + low;//取数组中随机下标
 Swap(arr, randomIndex, low);//与第一个数交换
 }
///<summary>
///三数取中确定基准元,将确定好的基准元与第一个数交换,无返回值
///</summary> 
 public static void PartitionMedianOfThree(int[] arr, int low, int high)
 {
 int mid = low + (high + -low)/2;
 if (arr[mid]> arr[high])
 {
 Swap(arr, mid, high);
 }
 if (arr[low]> arr[high])
 {
 Swap(arr, low, high);
 }
 if (arr[mid]> arr[low])
 {
 Swap(arr, mid, low);
 }//将中间大小的数与第一个数交换
 }
///<summary>
///插入排序
///</summary>
 public static void InsertSort(int[] arr, int low, int high)
 {
 for (int i = low + 1; i <= high; i++)
 {
 if (arr[i] <arr[i - 1])
 {
 for (int j = low; j <i; j++)
 {
 if (arr[j]> arr[i])
 {
 Swap(arr, i, j);
 }
 }
 }
 }
 }
///<summary>
///数组交换
///</summary>
 public static void Swap(int[] arr, int index1, int index2)
 {
 int temp = arr[index1];
 arr[index1] = arr[index2];
 arr[index2] = temp;
 }
 }
}

一. 快速排序的基本思想


快速排序使用分治的思想,通过一趟排序将待排序列分割成两部分,其中一部分记录的关键字均比另一部分记录的关键字小。之后分别对这两部分记录继续进行排序,以达到整个序列有序的目的。


二. 快速排序的三个步骤


1) 选择基准:在待排序列中,按照某种方式挑出一个元素,作为"基准"(pivot);


2) 分割操作:以该基准在序列中的实际位置,把序列分成两个子序列。此时,在基准左边的元素都比该基准小,在基准右边的元素都比基准大;


3) 递归地对两个序列进行快速排序,直到序列为空或者只有一个元素;


三. 选择基准元的方式


对于分治算法,当每次划分时,算法若都能分成两个等长的子序列时,那么分治算法效率会达到最大。也就是说,基准的选择是很重要的。选择基准的方式决定了两个分割后两个子序列的长度,进而对整个算法的效率产生决定性影响。


最理想的方法是,选择的基准恰好能把待排序序列分成两个等长的子序列。


方法一:固定基准元(基本的快速排序)


思想:取序列的第一个或最后一个元素作为基准元。

///<summary>
///1.0 固定基准元(基本的快速排序)
///</summary>
 public static void QsortCommon(int[] arr, int low, int high)
 {
 if (low> = high) return;//递归出口
 int partition = Partition(arr, low, high);//将> = x 的元素交换到右边区域,将 <= x 的元素交换到左边区域
 QsortCommon(arr, low, partition - 1);
 QsortCommon(arr, partition + 1, high);
 }
///<summary>
///固定基准元,默认数组第一个数为基准元,左右分组,返回基准元的下标
///</summary>
 public static int Partition(int[] arr, int low, int high)
 {
 int first = low;
 int last = high;
 int key = arr[low];//取第一个元素作为基准元
 while (first <last)
 {
 while (first <last && arr[last]> = key)
 last--;
 arr[first] = arr[last];
 while (first <last && arr[first] <= key)
 first++;
 arr[last] = arr[first];
 }
 arr[first] = key;//基准元居中
 return first;
 }

注意:基本的快速排序选取第一个或最后一个元素作为基准。但是,这是一直很不好的处理方法。
测试数据:

测试数据分析:如果输入序列是随机的,处理时间可以接受的。如果数组已经有序时,此时的分割就是一个非常不好的分割。因为每次划分只能使待排序序列减一,此时为最坏情况,快速排序沦为冒泡排序,时间复杂度为Θ(n^2)。而且,输入的数据是有序或部分有序的情况是相当常见的。因此,使用第一个元素作为基准元是非常糟糕的,为了避免这个情况,就引入了下面两个获取基准的方法。
方法二:随机基准元
思想:取待排序列中任意一个元素作为基准元。
引入的原因:在待排序列是部分有序时,固定选取基准元使快排效率底下,要缓解这种情况,就引入了随机选取基准元。
///<summary>
///2.0 随机基准元
///</summary>
 public static void QsortRandom(int[] arr, int low, int high)
 {
 if (low> = high) return;//递归出口
 PartitionRandom(arr, low, high);//随机基准元
 int partition = Partition(arr, low, high);//将> = x 的元素交换到右边区域,将 <= x 的元素交换到左边区域
 QsortRandom(arr, low, partition - 1);
 QsortRandom(arr, partition + 1, high);
 }
///<summary>
///随机基准元,将确定好的基准元与第一个数交换,无返回值
///</summary> 
 public static void PartitionRandom(int[] arr, int low, int high)
 {
 Random rd = new Random();
 int randomIndex = rd.Next() % (high - low) + low;//取数组中随机下标
 Swap(arr, randomIndex, low);//与第一个数交换
 }

测试数据:

测试数据分析::这是一种相对安全的策略。由于基准元的位置是随机的,那么产生的分割也不会总是会出现劣质的分割。在整个数组数字全相等时,仍然是最坏情况,时间复杂度是O(n^2)。实际上,随机化快速排序得到理论最坏情况的可能性仅为1/(2^n)。所以随机化快速排序可以对于绝大多数输入数据达到O(nlogn)的期望时间复杂度。一位前辈做出了一个精辟的总结:"随机化快速排序可以满足一个人一辈子的人品需求。"
方法三:三数取中
引入的原因:虽然随机选取基准时,减少出现不好分割的几率,但是还是最坏情况下还是O(n^2),要缓解这种情况,就引入了三数取中选取基准。
分析:最佳的划分是将待排序的序列分成等长的子序列,最佳的状态我们可以使用序列的中间的值,也就是第N/2个数。可是,这很难算出来,并且会明显减慢快速排序的速度。这样的中值的估计可以通过随机选取三个元素并用它们的中值作为基准元而得到。事实上,随机性并没有多大的帮助,因此一般的做法是使用左端、右端和中心位置上的三个元素的中值作为基准元。显然使用三数中值分割法消除了预排序输入的不好情形,并且减少快排大约14%的比较次数。
举例:待排序序列为:8 1 4 9 6 3 5 2 7 0
左边为:8,右边为0,中间为6
我们这里取三个数排序后,中间那个数作为枢轴,则枢轴为6
注意:在选取中轴值时,可以从由左中右三个中选取扩大到五个元素中或者更多元素中选取,一般的,会有(2t+1)平均分区法(median-of-(2t+1),三平均分区法英文为median-of-three。
具体思想:对待排序序列中low、mid、high三个位置上数据进行排序,取他们中间的那个数据作为基准,并用0下标元素存储基准。
即:采用三数取中,并用0下标元素存储基准。
///<summary>
///3.0 三数取中
///</summary>
 public static void QsortMedianOfThree(int[] arr, int low, int high)
 {
 if (low> = high) return;//递归出口
 PartitionMedianOfThree(arr, low, high);//三数取中
 int partition = Partition(arr, low, high);//将> = x 的元素交换到右边区域,将 <= x 的元素交换到左边区域
 QsortMedianOfThree(arr, low, partition - 1);
 QsortMedianOfThree(arr, partition + 1, high);
 }
///<summary>
///三数取中确定基准元,将确定好的基准元与第一个数交换,无返回值
///</summary> 
 public static void PartitionMedianOfThree(int[] arr, int low, int high)
 {
 int mid = low + (high + -low)/2;
 if (arr[mid]> arr[high])
 {
 Swap(arr, mid, high);
 }
 if (arr[low]> arr[high])
 {
 Swap(arr, low, high);
 }
 if (arr[mid]> arr[low])
 {
 Swap(arr, mid, low);
 }//将中间大小的数与第一个数交换
 }

测试数据:

测试数据分析:使用三数取中优势还是很明显的,但是还是处理不了重复数组。
四. 两种优化的方法
优化一:当待排序序列的长度分割到一定大小后,使用插入排序
原因:对于很小和部分有序的数组,快排不如插排好。当待排序序列的长度分割到一定大小后,继续分割的效率比插入排序要差,此时可以使用插排而不是快排。
截止范围:待排序序列长度N = 10,虽然在5~20之间任一截止范围都有可能产生类似的结果,这种做法也避免了一些有害的退化情形。
--摘自《数据结构与算法分析》Mark Allen Weiness 著
///<summary>
///4.0 三数取中+插排
///</summary> 
 public static void QsortThreeInsert(int[] arr, int low, int high)
 {
 if (high - low + 1 <10)
 {
 InsertSort(arr, low, high);
 return;
 }//插排,递归出口
 PartitionMedianOfThree(arr, low, high);//三数取中
 int partition = Partition(arr, low, high);//将> = x 的元素交换到右边区域,将 <= x 的元素交换到左边区域
 QsortMedianOfThree(arr, low, partition - 1);
 QsortMedianOfThree(arr, partition + 1, high);
 }

测试数据:

测试数据分析:针对随机数组,使用三数取中选择基准+插排,效率还是可以提高一点,真是针对已排序的数组,是没有任何用处的。因为待排序序列是已经有序的,那么每次划分只能使待排序序列减一。此时,插排是发挥不了作用的。所以这里看不到时间的减少。另外,三数取中选择基准+插排还是不能处理重复数组。
优化二:在一次分割结束后,可以把与Key相等的元素聚在一起,继续下次分割时,不用再对与key相等元素分割
举例:
待排序序列 1 4 6 7 6 6 7 6 8 6
三数取中选取基准:下标为4的数6
转换后,待分割序列:6 4 6 7 1 6 7 6 8 6
基准key:6
本次划分后,未对与key元素相等处理的结果:1 4 6 6 7 6 7 6 8 6
下次的两个子序列为:1 4 6 和 7 6 7 6 8 6
本次划分后,对与key元素相等处理的结果:1 4 6 6 6 6 6 7 8 7
下次的两个子序列为:1 4 和 7 8 7
经过对比,我们可以看出,在一次划分后,把与key相等的元素聚在一起,能减少迭代次数,效率会提高不少
具体过程:在处理过程中,会有两个步骤
第一步,在划分过程中,把与key相等元素放入数组的两端
第二步,划分结束后,把与key相等的元素移到枢轴周围
///<summary>
///5.0 三数取中+插排+聚集相同元素
///</summary> 
 public static void QsortThreeInsertGather(int[] arr, int low, int high)
 {
 if (high - low + 1 <10)
 {
 InsertSort(arr, low, high);
 return;
 }//插排,递归出口
 PartitionMedianOfThree(arr, low, high);//三数取中
//进行左右分组(处理相等元素)
 int first = low;
 int last = high;
 int left = low;
 int right = high;
 int leftLength = 0;
 int rightLength = 0;
 int key = arr[first];
 while (first <last)
 {
 while (first <last && arr[last]> = key)
 {
 if (arr[last] == key)//处理相等元素,将相等的元素放置数组两端
 {
 Swap(arr, last, right);
 right--;
 rightLength++;
 }
 last--;
 }
 arr[first] = arr[last];
 while (first <last && arr[first] <= key)
 {
 if (arr[first] == key)
 {
 Swap(arr, first, left);
 left++;
 leftLength++;
 }
 first++;
 }
 arr[last] = arr[first];
 }
 arr[first] = key;
//一次快排结束
//把与基准元key相同的元素移到最终位置周围
 int i = first - 1;
 int j = low;
 while (j <left && arr[i]!= key)
 {
 Swap(arr, i, j);
 i--;
 j++;
 }
 i = last + 1;
 j = high;
 while (j> right && arr[i]!= key)
 {
 Swap(arr, i, j);
 i++;
 j--;
 }
 QsortThreeInsertGather(arr, low, first - leftLength - 1);
 QsortThreeInsertGather(arr, first + rightLength + 1, high);
 }

测试数据:

测试数据分析:三数取中+插排+聚集相等元素的组合,效果竟然好的出奇。
原因:在数组中,如果有相等的元素,那么就可以减少不少冗余的划分。这点在重复数组中体现特别明显啊。
其实这里,插排的作用还是不怎么大的。
以下是全部的测试程序源码:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Diagnostics;
using System.Threading;
namespace Sort
{
 class Program
 {
 static void Main(string[] args)
 {
//开启10M的堆栈空间的线程
 ThreadStart ts = new ThreadStart(Sort.DoQsort);
 Thread thread = new Thread(ts, 10000000);
 thread.Start();
 }
 }
 class Sort
 {
 public static void DoQsort()
 {
 int[] arr = new int[100000];//10W个空间大小的数组
//Random rd = new Random();
//for (int i = 0; i <arr.Length; i++)//随机数组
//{
//arr[i] = rd.Next();
//}
//for (int i = 0; i <arr.Length; i++)//升序数组
//{
//arr[i] = i;
//}
//for (int i = 0; i <arr.Length; i++)//降序数组
//{
//arr[i] = arr.Length - 1 - i;
//}
 for (int i = 0; i <arr.Length; i++)//重复数组
 {
 arr[i] = 5768461;
 }
 Stopwatch watch = new Stopwatch();
 watch.Start();//开始计时
//QsortCommon(arr, 0, arr.Length - 1);//固定基准元
//QsortRandom(arr, 0, arr.Length - 1);//随机基准元
//QsortMedianOfThree(arr, 0, arr.Length - 1);//三数取中
//QsortThreeInsert(arr, 0, arr.Length - 1);//三数取中+插排
 QsortThreeInsertGather(arr, 0, arr.Length - 1);//三数取中+插排+聚集相同元素
 watch.Stop();//计时结束
 Console.WriteLine(watch.ElapsedMilliseconds.ToString());
 }
///<summary>
///1.0 固定基准元(基本的快速排序)
///</summary>
 public static void QsortCommon(int[] arr, int low, int high)
 {
 if (low> = high) return;//递归出口
 int partition = Partition(arr, low, high);//将> = x 的元素交换到右边区域,将 <= x 的元素交换到左边区域
 QsortCommon(arr, low, partition - 1);
 QsortCommon(arr, partition + 1, high);
 }
///<summary>
///2.0 随机基准元
///</summary>
 public static void QsortRandom(int[] arr, int low, int high)
 {
 if (low> = high) return;//递归出口
 PartitionRandom(arr, low, high);//随机基准元
 int partition = Partition(arr, low, high);//将> = x 的元素交换到右边区域,将 <= x 的元素交换到左边区域
 QsortRandom(arr, low, partition - 1);
 QsortRandom(arr, partition + 1, high);
 }
///<summary>
///3.0 三数取中
///</summary>
 public static void QsortMedianOfThree(int[] arr, int low, int high)
 {
 if (low> = high) return;//递归出口
 PartitionMedianOfThree(arr, low, high);//三数取中
 int partition = Partition(arr, low, high);//将> = x 的元素交换到右边区域,将 <= x 的元素交换到左边区域
 QsortMedianOfThree(arr, low, partition - 1);
 QsortMedianOfThree(arr, partition + 1, high);
 }
///<summary>
///4.0 三数取中+插排
///</summary> 
 public static void QsortThreeInsert(int[] arr, int low, int high)
 {
 if (high - low + 1 <10)
 {
 InsertSort(arr, low, high);
 return;
 }//插排,递归出口
 PartitionMedianOfThree(arr, low, high);//三数取中
 int partition = Partition(arr, low, high);//将> = x 的元素交换到右边区域,将 <= x 的元素交换到左边区域
 QsortMedianOfThree(arr, low, partition - 1);
 QsortMedianOfThree(arr, partition + 1, high);
 }
///<summary>
///5.0 三数取中+插排+聚集相同元素
///</summary> 
 public static void QsortThreeInsertGather(int[] arr, int low, int high)
 {
 if (high - low + 1 <10)
 {
 InsertSort(arr, low, high);
 return;
 }//插排,递归出口
 PartitionMedianOfThree(arr, low, high);//三数取中
//进行左右分组(处理相等元素)
 int first = low;
 int last = high;
 int left = low;
 int right = high;
 int leftLength = 0;
 int rightLength = 0;
 int key = arr[first];
 while (first <last)
 {
 while (first <last && arr[last]> = key)
 {
 if (arr[last] == key)//处理相等元素
 {
 Swap(arr, last, right);
 right--;
 rightLength++;
 }
 last--;
 }
 arr[first] = arr[last];
 while (first <last && arr[first] <= key)
 {
 if (arr[first] == key)
 {
 Swap(arr, first, left);
 left++;
 leftLength++;
 }
 first++;
 }
 arr[last] = arr[first];
 }
 arr[first] = key;
//一次快排结束
//把与基准元key相同的元素移到最终位置周围
 int i = first - 1;
 int j = low;
 while (j <left && arr[i]!= key)
 {
 Swap(arr, i, j);
 i--;
 j++;
 }
 i = last + 1;
 j = high;
 while (j> right && arr[i]!= key)
 {
 Swap(arr, i, j);
 i++;
 j--;
 }
 QsortThreeInsertGather(arr, low, first - leftLength - 1);
 QsortThreeInsertGather(arr, first + rightLength + 1, high);
 }
///<summary>
///固定基准元,默认数组第一个数为基准元,左右分组,返回基准元的下标
///</summary>
 public static int Partition(int[] arr, int low, int high)
 {
 int first = low;
 int last = high;
 int key = arr[low];//取第一个元素作为基准元
 while (first <last)
 {
 while (first <last && arr[last]> = key)
 last--;
 arr[first] = arr[last];
 while (first <last && arr[first] <= key)
 first++;
 arr[last] = arr[first];
 }
 arr[first] = key;//基准元居中
 return first;
 }
///<summary>
///随机基准元,将确定好的基准元与第一个数交换,无返回值
///</summary> 
 public static void PartitionRandom(int[] arr, int low, int high)
 {
 Random rd = new Random();
 int randomIndex = rd.Next() % (high - low) + low;//取数组中随机下标
 Swap(arr, randomIndex, low);//与第一个数交换
 }
///<summary>
///三数取中确定基准元,将确定好的基准元与第一个数交换,无返回值
///</summary> 
 public static void PartitionMedianOfThree(int[] arr, int low, int high)
 {
 int mid = low + (high + -low)/2;
 if (arr[mid]> arr[high])
 {
 Swap(arr, mid, high);
 }
 if (arr[low]> arr[high])
 {
 Swap(arr, low, high);
 }
 if (arr[mid]> arr[low])
 {
 Swap(arr, mid, low);
 }//将中间大小的数与第一个数交换
 }
///<summary>
///插入排序
///</summary>
 public static void InsertSort(int[] arr, int low, int high)
 {
 for (int i = low + 1; i <= high; i++)
 {
 if (arr[i] <arr[i - 1])
 {
 for (int j = low; j <i; j++)
 {
 if (arr[j]> arr[i])
 {
 Swap(arr, i, j);
 }
 }
 }
 }
 }
///<summary>
///数组交换
///</summary>
 public static void Swap(int[] arr, int index1, int index2)
 {
 int temp = arr[index1];
 arr[index1] = arr[index2];
 arr[index2] = temp;
 }
 }
}



Copyright © 2011 Dowemo All rights reserved.    Creative Commons   AboutUs