1.排序的概念及其運用

1.1 排序的概念

排序：所謂排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作。

穩定性：假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經過排序，這些記錄的相對次

序保持不變，即在原序列中，r[i]=r[j]，且 r[i]在 r[j]之前，而在排序后的序列中，r[i]仍在 r[j]之前，則稱這種排

序算法是穩定的；否則稱為不穩定的。

內部排序：數據元素全部放在內存中的排序。

外部排序：數據元素太多不能同時放在內存中，根據排序過程的要求不能在內外存之間移動數據的排序。

1.2 常見的排序算法

排序的相關接口：

//排序實現接口
// 插入排序 
void InsertSort(int* a, int n);
// 希爾排序
void ShellSort(int* a, int n); 
// 選擇排序 
void SelectSort(int* a, int n); 
// 堆排序 
void AdjustDwon(int* a, int n, int root); 
void HeapSort(int* a, int n); 
// 冒泡排序 
void BubbleSort(int* a, int n);
// 快速排序遞歸實現 
// 快速排序hoare版本 
int PartSort1(int* a, int left, int right); 
// 快速排序挖坑法 
int PartSort2(int* a, int left, int right); 
// 快速排序前后指針法 
int PartSort3(int* a, int left, int right); 
void QuickSort(int* a, int left, int right); 
// 快速排序 非遞歸實現 
void QuickSortNonR(int* a, int left, int right)；
// 歸并排序遞歸實現 
void MergeSort(int* a, int n)；
// 歸并排序非遞歸實現 
void MergeSortNonR(int* a, int n)；
// 計數排序 
void CountSort(int* a, int n)；

排序算法的原理和實現：

【數據結構】揭秘直接插入排序：玩撲克也能學算法-CSDN博客

【數據結構】希爾排序：高效分組的插入排序優化-CSDN博客

【數據結構】直接選擇排序-CSDN博客

【數據結構】快速排序算法精髓解析-CSDN博客

【數據結構】遞歸與非遞歸：歸并排序全解析-CSDN博客