目錄
一、概述
二、常見的排序算法
2.1 冒泡排序
2.1.1 定義
2.1.2 C語言實現
2.2 快速排序
2.2.1 定義
2.2.2 C語言實現
2.3 插入排序
2.3.1 定義
2.3.2 C語言實現
2.4 希爾排序
2.4.1 定義
2.4.2 C語言實現
2.5 歸并排序
2.5.1 定義
2.5.2 C語言實現
2.6 基數排序
2.6.1 定義
2.6.2 C語言實現
三、排序算法的空間、時間復雜度、穩定性
一、概述
排序算法是《數據結構與算法》中最基本的算法之一。排序算法可以分為內部排序和外部排序，內部排序是數據記錄在內存中進行排序，而外部排序是因排序的數據很大，一次不能容納全部的排序記錄，在排序過程中需要訪問外存。常見的內部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數排序等。
二、常見的排序算法
2.1 冒泡排序
2.1.1 定義
冒泡排序是一種簡單的排序算法，它重復地遍歷要排序的數列，一次比較兩個元素，如果它們的順序錯誤就把它們交換過來。重復進行直到沒有再需要交換的元素，這意味著數列已經排序完成。
2.1.2 C語言實現
這段代碼首先定義了一個冒泡排序函數bubble_sort，它接受一個整型數組和數組的長度作為參數。然后定義了兩個輔助函數print_array用于打印數組和main函數作為程序的入口。在main函數中，我們首先打印原始數組，然后調用冒泡排序函數進行排序，并再次打印排序后的數組。
#include <stdio.h>void bubble_sort(int arr[], int len) {int i, j, temp;for (i = 0; i < len - 1; i++)for (j = 0; j < len - 1 - i; j++)if (arr[j] > arr[j + 1]) {temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}
}void print_array(int arr[], int len) {int i;for (i = 0; i < len; i++)printf("%d ", arr[i]);printf("\n");
}int main() {int arr[] = {64, 34, 25, 12, 22, 11, 90};int len = (int) sizeof(arr) / sizeof(*arr);printf("Original array: ");print_array(arr, len);bubble_sort(arr, len);printf("Sorted array: ");print_array(arr, len);return 0;
}2.2 快速排序
2.2.1 定義
快速排序作為多種排序方法中效率最高的一種，其底層原理被廣泛運用，他的核心思想與二叉樹結構中的遞歸邏輯相似，首先標記一個元素作為基準點，然后利用該基準點把數組分成左右兩個區間，并且使小于該基準點的元素放在左區間，大于該基準點的元素放在右區間，如此反復遞歸，直到數組為一個有序數組。
2.2.2 C語言實現
這段代碼首先定義了一個輔助函數swap用于交換數組中的元素。然后定義了partition函數來選擇一個基準點并重新排列數組，使得比基準點小的元素都在它的左側，比基準點大的元素都在它的右側。最后，quickSort函數遞歸地對數組的左右部分進行排序。printArray函數用于打印排序后的數組。在main函數中，我們定義了一個數組并對它進行排序，然后打印排序結果。
#include <stdio.h>void swap(int* a, int* b) {int t = *a;*a = *b;*b = t;
}int partition (int arr[], int low, int high) {int pivot = arr[high];int i = (low - 1);for (int j = low; j <= high - 1; j++) {if (arr[j] < pivot) {i++;swap(&arr[i], &arr[j]);}}swap(&arr[i + 1], &arr[high]);return (i + 1);
}void quickSort(int arr[], int low, int high) {if (low < high) {int pi = partition(arr, low, high);quickSort(arr, low, pi
