五種基礎排序-升序實現

插入排序

構建有序序列，對於未排序數據，在已排序序列中從後向前掃描，找到相應位置並插入。

void InsertSort(int buf[], int bufsize)
{
    for (int i = 1; i < bufsize; i++){
        int temp = buf[i];
        int j = i - 1;
        // 只移動，不插入
        while (j >= 0 && buf[j] > temp){
            buf[j + 1] = buf[j];
            j--;
        }
        // 統一插入：位置是 j+1
        buf[j + 1] = temp;
    }
}

冒泡排序

重複地走訪要排序的數列，依次比較兩個元素，如果它們的順序錯誤就把它們交換過來。走訪數列的工作是重複進行直到沒有再需要交換，然後排序完成

void BubbleSort(int buf[], int bufsize)
{
	int Temp = 0;
	//i從1開始，表示第一輪比較
	for(int i=1;i<bufsize;i++){
		//每輪比較完都會找到一個最大的數放在數組最後，下輪需要參與比較的數減低1
		for (int j=0;j<bufsize-i;++j){

			if(buf[j]>buf[j+1]){
				Temp = buf[j];
				buf[j] = buf[j+1];
				buf[j+1] = Temp;
			}
		}
	}
}

選擇排序

每一次從待排序的數據元素中選出最小（或最大）的一個元素，存放在序列的起始位置，然後，再從剩餘未排序元素中繼續尋找最小（大）元素，放到已排序序列的末尾。直到所有元素均排序完畢。

void SelectSort(int buf[], int bufsize)
{
    //// 當只剩一個元素時，沒比較對象，自身就是最小的，所以 n < bufsize - 1，無需再比較
    for (int n = 0; n < bufsize - 1; n++) {
        int index = n;// 假設當前無序部分的第一個元素（下標 n）是最小的
                        // index 用於記錄當前找到的最小元素的下標
        for (int m = n + 1; m < bufsize; m++) {
            // 如果發現比 buf[index] 更小的元素
            if (buf[m] < buf[index]) {
                index = m;
            }
        }
        // 使用臨時變量安全交換
        if (index != n) {  // 避免不必要的交換
            int temp = buf[n];
            buf[n] = buf[index];
            buf[index] = temp;
        }
    }
}

快速排序

把一個序列分為較小和較大的兩個子序列，然後遞歸地排序兩個子序列。具體過程是選擇一個“基準”元素，將數組劃分為比基準小的元素和比基準大的元素兩部分，再對這兩部分分別遞歸進行快速排序。

// buf[]: 待排序的數組
// low:  當前排序區間的起始下標
// high: 當前排序區間的結束下標
void QuickSort(int buf[],int low,int high)
{	
	int l=low,h=high;
	int temp;
	// 遞歸終止條件：如果區間無效（low >= high），直接返回
	if(low<high)
	{
		temp=buf[low];// 選擇第一個元素作為“基準值”
		while(l!=h)
		{
			// 步驟1：從右往左找，跳過比基準大的元素
            // 直到找到一個小於等於基準的元素，準備“填坑”
			while(l<h&&buf[h]>temp)h--;
			if(l<h)
			{
				buf[l]= buf[h];
				++l;
			}
			// 步驟2：從左往右找，跳過比基準小的元素
            // 直到找到一個大於等於基準的元素，準備“填坑”
			while(l<h&&buf[l]<temp)l++;
			if(l<h)
			{
				buf[h]=buf[l];
				--h;
			}
			// 如此反覆，左右交替“填坑”，直到 l == h
		}
		buf[l] = temp;
		// 此時，基準左邊都小於它，右邊都大於它
        // 遞歸對左右兩個子區間進行快速排序
		QuickSort(buf,low,l-1);
		QuickSort(buf,l+1,high);
	}
}

計數排序

計數排序不是基於比較的排序算法，它的核心在於將輸入的數據值轉化為鍵存儲在額外開闢的數組空間中。作為一種線性時間複雜度的排序，計數排序要求輸入的數據必須是有確定範圍的整數。（該版本不適合有重複元素的穩定排序，且輸出到B數組）

void CountSort(int A[],int B[],int size)
{
	int cnt;//用於統計A[]中比A[i]小的元素個數
	for(int i = 0;i < size;i++)
	{
		cnt = 0;
		for(int j=0;j<size;j++)
		{
			if(A[j]<A[i]){
				cnt++;
			}
		}
        //A[]中比A[i]小的元素個數為cnt個，A[i]值就放到B[cnt]
		B[cnt]=A[i];
	}
}

測試

#include <stdio.h>

/**
	五種排序函數定義
*/

// 打印數組
void PrintArray(int arr[], int size) {
    for (int i = 0; i < size; ++i) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main(int argc, char const *argv[])
{
	int arr[] = {14, 23, 12, 5, 8, 3, 9, 10, 33, 6};
    int size = sizeof(arr) / sizeof(arr[0]);

    printf("原始數組: ");
    PrintArray(arr, size);

    // 測試 InsertSort
    int arr1[size];
    for (int i = 0; i < size; i++) arr1[i] = arr[i];
    InsertSort(arr1, size);
    printf("插入排序後: ");
    PrintArray(arr1, size);

    // 測試 BubbleSort
    int arr2[size];
    for (int i = 0; i < size; i++) arr2[i] = arr[i];
    BubbleSort(arr2, size);
    printf("冒泡排序後: ");
    PrintArray(arr2, size);

    // 測試 SelectSort
    int arr3[size];
    for (int i = 0; i < size; i++) arr3[i] = arr[i];
    SelectSort(arr3, size);
    printf("選擇排序後: ");
    PrintArray(arr3, size);

    // 測試 QuickSort
    int arr4[size];
    for (int i = 0; i < size; i++) arr4[i] = arr[i];
    QuickSort(arr4, 0, size - 1);
    printf("快速排序後: ");
    PrintArray(arr4, size);

    // 測試 CountSort
    int arr5[size];  // 輸出數組
    CountSort(arr, arr5, size);
    printf("計數排序後: ");
    PrintArray(arr5, size);

    return 0;
}

測試結果