今天重溫了下排序算法，包括冒泡排序法和直接排序法，這些都比較簡單，只是快速排序法比較難，於是重點研究了下。
先說一說原理：快速排序法是采用遞歸的方式對待排序的數列進行若干次的操作,每次操作使得被操作的數列部分以某個元素為分界值分成兩部分,一部分小於該分界值,另一部分大於該分界值.該分界值一般被稱為"樞軸". 一般先以左邊第一個數作為分界值，將數列按該分界值分成左右兩部分，左邊部分小於該分界值，右邊部分大於該分界值，然後再對左右兩部分做重復的操作，直到最後完成排序。
以數列 14,11,25,37,9,28 為例,詳細描述執行一趟快速排序的算法:
1,選擇待排序數列的樞軸,一般以數列的首元素作為樞軸.此數列中,我們選擇首元素14作為樞軸,nPivot = 14.
2,設定兩個指針 i 和 j ,分別指向數列的首元素和尾元素. i 指向首元素14, j 指向尾元素28.示意圖如下:
3,向前移動尾指針 j ,使其指向從數列尾部算起首個小於樞軸(即14)的元素,並將該元素置換到頭指針 i 指向的位置._nArray[i] =_nArray[j].示意圖如下:
首次執行該操作時 i 指針指向處的值實際上就是樞軸的值,此處的操作可以理解為 i 指針指向處的值已在之前被置換到樞軸中,此時, i 指向處已經是一個空位,在此時用找到的小於樞軸的元素填在此處.
4,向後移動頭指針 i ,使其指向從數列頭部算起首個大於樞軸(即14)的元素,並將該元素置換到尾指針 j 指向的位置._nArray[j] =_nArray[i].示意圖如下:
此處同樣可以理解為 j 指針指向處的值已在上一步操作中置換了出去. j 處已是一個空位.
5,如此重復執行步驟3和步驟4,直至 i==j 時結束該循環.
6,退出了該循環後, i 與 j 必定指向同一位置.在該位置的前部元素,其值均小於樞軸.而在該位置的後部元素,其值均大於樞軸.顯而易見,此時 i 和 j 同時指向的位置就應該是樞軸的"新家"._nArray[i]=nPivot.如下圖:
至此,一趟排序結束.待排序數列的首元素將該數列分成了比其小和比其大的兩部分.如下圖:
接著,我們對這一大一小兩部分子數列執行相同的排序操作.
如此"遞歸",直至對整個數列完成排序操作.
以下是c#實現代碼
static void Main(string[] args)
{
Console.WriteLine("請輸入待排序數列(以\",\"分割):");
string _s = Console.ReadLine();
string[] _sArray = _s.Split(",".ToCharArray());
int _nLength = _sArray.Length;
int[] _nArray = new int[_nLength];
for (int i = 0; i < _nLength; i++)
{
_nArray[i] = Convert.ToInt32(_sArray[i]);
}
var list = _nArray.ToList();
QuickSort(list, 0, _nLength - 1);
foreach (var i in list)
{
Console.WriteLine(i.ToString());
}
while (true)
{
Thread.Sleep(10000);
}
}
//獲取按樞軸值左右分流後樞軸的位置
private static int Division(List<int> list, int left, int right)
{
while (left < right)
{
int num = list[left]; //將首元素作為樞軸
if (num > list[left + 1])
{
list[left] = list[left + 1];
list[left + 1] = num;
left++;
}
else
{
int temp = list[right];
list[right] = list[left + 1];
list[left + 1] = temp;
right--;
}
Console.WriteLine(string.Join(",", list));
}
Console.WriteLine("--------------\n");
return left; //指向的此時樞軸的位置
}
private static void QuickSort(List<int> list, int left, int right)
{
if (left < right)
{
int i = Division(list, left, right);
//對樞軸的左邊部分進行排序
QuickSort(list, i + 1, right);
//對樞軸的右邊部分進行排序
QuickSort(list, left, i - 1);
}
}
這是結構體指針中的一個符號，給你寫個程序解釋一下吧，例如：
#include<stdio.h>
struct STU //定義一個結構體
{
int num;
}stu;
int main()
{
struct STU *p; //定義一個結構體指針
p=stu; //p指向stu這個結構體變量
stu.num=100; //給結構體成員num附個初值
printf("%d",p->num); //輸出stu中的num的值
return；
}
看到了吧，->的作法就是在引用結構體中的變量！！
形式如：p->結構體成員（如p->num）
他的作用相當於stu.num或(*p).num
不知道這樣解釋你明不明白、、、、、不懂了call我，O(∩_∩)O~
望采納。
這是結構體指針中的一個符號，給你寫個程序解釋一下吧，例如：
#include<stdio.h>
struct STU //定義一個結構體
{
int num;
}stu;
int main()
{
struct STU *p; //定義一個結構體指針
p=stu; //p指向stu這個結構體變量
stu.num=100; //給結構體成員num附個初值
printf("%d",p->num); //輸出stu中的num的值
return；
}
看到了吧，->的作法就是在引用結構體中的變量！！
形式如：p->結構體成員（如p->num）
他的作用相當於stu.num或(*p).num
不知道這樣解釋你明不明白、、、、、不懂了call我，O(∩_∩)O~
望采納。
