クイックソートアルゴリズムについて(90%の人がその原理を知らず、99.9%の人が正常に書けないアルゴリズムです.)
15484 ワード
一、奇妙な現象
研究は急速に並べ替えて長い間、1つの奇妙な実情を発見しました:このアルゴリズムは説明するのが簡単で、正しいことを書くのは本当に容易ではありません.優れた高速ソートアルゴリズムを書くのはさらに難しい.
道理でこのアルゴリズムが提出されてから長い間正しいアルゴリズムを書いた人がいて、長い間優秀なバージョンが出てきたのも無理はない.
二、原理説明数列から「基準」(pivot)と呼ばれる要素を選択し、 は数列を並べ替え、すべての要素が基準値より小さいものは基準の前に配置され、すべての要素が基準値より大きいものは基準の後ろに配置されます(同じ数は任意の側に配置できます).このパーティションが終了すると、基準は数列の中間位置にあります.これをパーティション操作と呼ぶ. 再帰(recursive)基準値より小さい要素のサブ数列と基準値より大きい要素のサブ数列とを並べ替える.
三、最もわかりやすいバージョン
1つのList形式の配列は、その中の1つ目を基準として、残りのデータを遍歴する、それから2つの左右のListを作成し、大きいのは右、小さいのは左を置く.そして、左右のListそれぞれに対して上記のような操作を行う.
詳細はコードを参照
四、正しいが最適化されていないバージョン
研究は急速に並べ替えて長い間、1つの奇妙な実情を発見しました:このアルゴリズムは説明するのが簡単で、正しいことを書くのは本当に容易ではありません.優れた高速ソートアルゴリズムを書くのはさらに難しい.
道理でこのアルゴリズムが提出されてから長い間正しいアルゴリズムを書いた人がいて、長い間優秀なバージョンが出てきたのも無理はない.
二、原理説明
三、最もわかりやすいバージョン
1つのList形式の配列は、その中の1つ目を基準として、残りのデータを遍歴する、それから2つの左右のListを作成し、大きいのは右、小さいのは左を置く.そして、左右のListそれぞれに対して上記のような操作を行う.
詳細はコードを参照
using System;
using System.Collections.Generic;
using System.Text;
namespace test
{
class Program
{
static void Main(string[]args)
{
List<int> array=new List<int>();
array.AddRange(new int[]{3,2,9,5,8,6,23,23,222,12,21});
var t1=DateTime.Now.Ticks;
sort(array);
var t2=DateTime.Now.Ticks;
Console.WriteLine(t2-t1);
Console.ReadLine();
}
static int Count=0;
public static void sort(List<int> array)
{
var guid=Count++;
Console.WriteLine();
Console.Write(" :("+guid+")");
Show(array);
if (array.Count<=1) {
return;
}
if (array.Count==2) {
if (array[0]>array[1]) {
var temp=array[0];
array[0]=array[1];
array[1]=temp;
Console.Write(" :");
Show(array);
}
}
else{
var xData=array[0];
var leftList=new List<int>();
var rightList=new List<int>();
for (int i = 1; i < array.Count; i++) {
var t=array[i];
if (t<=xData) {
leftList.Add(t);
}else{
rightList.Add(t);
}
}
Console.WriteLine(" :"+xData);
Console.Write(" ("+guid+"):");
Show(leftList);
Console.Write(" ("+guid+"):");
Show(rightList);
sort(leftList);
Console.Write(" ( )("+guid+"):");
Show(leftList);
sort(rightList);
Console.Write(" ( )("+guid+"):");
Show(rightList);
array.Clear();
array.AddRange(leftList);
array.Add(xData);
array.AddRange(rightList);
Console.Write(" ("+guid+"):");
Show(array);
Console.WriteLine();
leftList.Clear();
rightList.Clear();
}
}
public static void Show(List<int>array){
foreach (var a in array) {
Console.Write(a+",");
}
Console.WriteLine();
}
}
}
四、正しいが最適化されていないバージョン
using System;
namespace Sort
{
class Program
{
static void Main(string[] args)
{
string result = string.Empty;
int[] unsort = { 2, 0, 3, 7, 5,6 };
//
QuickSort(unsort, 0, unsort.Length - 1);
Console.ReadLine();
}
/// <summary>
///
/// </summary>
/// <param name="unsort"> </param>
/// <param name="left"> </param>
/// <param name="right"> </param>
public static void QuickSort(int[] unsort, int left, int right)
{
if (left < right)
{
//
int midPosition = GetSplitNum(unsort, left, right);
//
QuickSort(unsort, left, midPosition - 1);
QuickSort(unsort, midPosition + 1, right);
}
}
static int ORDER_INDEX=1;
/// <summary>
///
/// </summary>
/// <param name="unsort"> </param>
/// <param name="left"> </param>
/// <param name="right"> </param>
public static int GetSplitNum(int[] unsort, int left, int right)
{
int splitNum = unsort[left];
while (left < right)
{
/**
*
* （1） ，
* （2） ，
* */
while (left < right && splitNum <= unsort[right])
{
right--;
}
unsort[left] = unsort[right];
GetPrint(unsort);
/**
*
* （1） ，
* （2） ，
* */
while (left < right && splitNum >= unsort[left])
{
left++;
}
unsort[right] = unsort[left];
GetPrint(unsort);
}
// ，
unsort[left] = splitNum;
Console.WriteLine(string.Format(" {0} ",(ORDER_INDEX++)));
GetPrint(unsort);
return left;
}
/// <summary>
///
/// </summary>
/// <param name="unsort"> </param>
public static string GetPrint(int[] unsort)
{
string result = string.Empty;
foreach (int n in unsort)
{
if (!string.IsNullOrEmpty(result))
{
result += string.Format("->{0}", n);
}
else
{
result = string.Format("{0}", n);
}
}
Console.WriteLine(result);
return result;
}
public static string GetPrint(int[] unsort,int replaceIndex)
{
string result = string.Empty;
foreach (int n in unsort)
{
if (!string.IsNullOrEmpty(result))
{
result += string.Format("->{0}", n);
}
else
{
result = string.Format("{0}", n);
}
}
Console.WriteLine(result+" ==>"+replaceIndex);
return result;
}
}
}