面試常考各類排序演算法總結.(c#)

前言面試以及考試過程中必會出現一道排序演算法面試題，為了加深對排序演算法的理解，在此我對各種排序演算法做個總結歸納。 1、冒泡排序演算法(BubbleSort) 1.1 演算法描述（1）比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。（2）對每一對相鄰元素做同樣的工作，從開始第一對到結尾的最後一對 ...

前言

面試以及考試過程中必會出現一道排序演算法面試題，為了加深對排序演算法的理解，在此我對各種排序演算法做個總結歸納。

1、冒泡排序演算法(BubbleSort)

1.1 演算法描述

（1）比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。

（2）對每一對相鄰元素做同樣的工作，從開始第一對到結尾的最後一對。在這一點，最後的元素應該會是最大的數。

（3）針對所有的元素重覆以上的步驟，除了最後一個。

（4）持續每次對越來越少的元素重覆上面的步驟，直到沒有任何一對數字需要比較。

最好時間複雜度O（n）最壞時間複雜度O（n2）

1.2 動圖演示

1.3 C#代碼實現

public Class SortDemo
{
     public void BubbleSort(int arr)
     {
            int temp=0;
          //需要走arr.Length-1 趟
           for(int i=0;i<arr.Length-1;i++)
           {
                 //每一趟需要比較次數
                 for(int j=0,j<arr.Length-i-1;j++)
                 {
                     //升序排序
                      if(arr[j]>arr[j+1])
                      {
                               temp=arr[j];//將較大的變數保存在臨時變數
                               arr[j]=arr[j+1]；
                               arr[j+1]=temp;
                       }   
                 }
            }
         
     }
}

2、直接插入排序(InsertionSort)

2.1 演算法描述

（1）從第一個元素開始，該元素可以認為已經被排序；

（2）取出下一個元素，在已經排序的元素序列中從後向前掃描；

（3）如果該元素（已排序）大於新元素，將該元素移到下一位置；

（4）重覆步驟3，直到找到已排序的元素小於或者等於新元素的位置；

（5）將新元素插入到該位置後；

（6）重覆步驟2~5。

2.2 動圖演示

2.3 C#代碼實現

public Class SortDemo
{
      public void InsertionSort(int[] arr)
      {
             int temp=0;
             //遍歷待插入的數(從第二位開始)
             for(int i=1;i<arr.Length;i++)
             {

　　　　　　　　　　　　temp=arr[i];//待插入的數

　　　　　　　　　　　　int j=i-1;//（j為已排序的待插入的位置序號）
                     
                     //若已排序的數大於待插入數，則往後移一位
                     while(j>=0&&arr[j]>temp)
                     {
                            arr[j+1]=arr[j];
                            j--;
                      }
                     arr[j+1]=temp;//將待插入的數放入插入位置
              }
      }
}

3、選擇排序(SelectionSort)

3.1 演算法描述

選擇排序(Selection-sort)是一種簡單直觀的排序演算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然後，再從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。

（1）初始狀態：無序區為R[1..n]，有序區為空；

（2）第i趟排序(i=1,2,3…n-1)開始時，當前有序區和無序區分別為R[1..i-1]和R(i..n）。該趟排序從當前無序區中-選出關鍵字最小的記錄 R[k]，將它與無序區的第1個記錄R交換，使R[1..i]和R[i+1..n)分別變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區；

（3）n-1趟結束，數組有序化了。

3.2 動圖演示

3.3 C#代碼實現

public void SelectionSort(int[] arr)
     {
         int temp;
         for(int i=0;i<arr.Length-1;i++)
         {
             int minVal=arr[i];
             int minIndex=i;
             for(int j=i+1;j<arr.Length;j++)
             {
                 if(minVal>arr[j])
                 { 
                    minVal=arr[j];
                    minIndex=j;
                 }
             }
             temp=arr[i];
             arr[i]=minVal;
             arr[minIndex]=temp;
         }
 
     }
}

4、快速排序(QuickSort)

4.1 演算法描述

（1）從數列中挑出一個元素，稱為 “基準”（pivot）；

（2）重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）。在這個分區退出之後，該基準就處於數列的中間位置。這個稱為分區（partition）操作；

（3）遞歸地（recursive）把小於基準值元素的子數列和大於基準值元素的子數列排序。

快速排序法是採用遞歸的方式對待排序的數列進行若幹次的操作,每次操作使得被操作的數列部分以某個元素為分界值分成兩部分,一部分小於該分界值,另一部分大於該分界值.該分界值一般被稱為"樞軸". 一般先以左邊第一個數作為分界值，將數列按該分界值分成左右兩部分，左邊部分小於該分界值，右邊部分大於該分界值，然後再對左右兩部分做重覆的操作，直到最後完成排序。

以數列 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.如下圖:

至此,一趟排序結束.待排序數列的首元素將該數列分成了比其小和比其大的兩部分.如下圖:

接著,我們對這一大一小兩部分子數列執行相同的排序操作.

如此"遞歸",直至對整個數列完成排序操作.

4.2 動圖演示

4.3 c#代碼實現

class Program { static void Main(string[] args) { Console.WriteLine("請輸入待排序數列(以\",\"分割):"); int[] arr = new int[] { 10, 11, 44, 9, 8, 19, 45, 20, 24, 11, 3, 7 }; Sort(arr, 0, arr.Length - 1); foreach (var i in arr) { Console.WriteLine(i.ToString()); } }

/// <summary>
/// 排序
/// </summary>
/// <param name="array">要排序的數組</param>
/// <param name="low">下標開始位置，向右查找</param>
/// <param name="high">下標開始位置，向左查找</param>
public static void Sort(int[] array, int low, int high)
{
if (low >= high)
return;
//完成一次單元排序
int index = SortUnit(array, low, high);
//遞歸調用，對左邊部分的數組進行單元排序
Sort(array, low, index - 1);
//遞歸調用，對右邊部分的數組進行單元排序
Sort(array, index + 1, high);
}

/// <summary>

/// 單元排序

/// </summary>
/// <param name="array">要排序的數組</param>
/// <param name="low">下標開始位置，向右查找</param>
/// <param name="high">下標開始位置，向右查找</param>
/// <returns>每次單元排序的停止下標</returns>
public static int SortUnit(int[] array, int low, int high)
{
int key = array[low];//基準數
while (low < high)
{
//從high往前找小於或等於key的值
while (low < high && array[high] > key)
high--;
//比key小開等的放左邊
array[low] = array[high];
//從low往後找大於key的值
while (low < high && array[low] <= key)
low++;
//比key大的放右邊
array[high] = array[low];
}
//結束迴圈時，此時low等於high，左邊都小於或等於key，右邊都大於key。將key放在游標當前位置。
array[low] = key;
return high;
}

}

文章參考摘自：https://www.cnblogs.com/yundan/p/4022056.html https://www.cnblogs.com/geduocoding/p/7097870.html