一、排序基本概念
1.就地排序：使用恒定的額外空間來產生輸出
就地排序只是在原數組空間進行排序處理，也就是輸入的數組和得到的數組是同一個
2.內部排序和外部排序：待排序數據可以一次性載入到內存中為內部排序，反之數據量過大就是外部排序
本科階段幾乎都是內部排序
3.穩定排序：排序前后序列中鍵值相等的元素在相對位置不發生變化的就是穩定排序
4.哪些排序是穩定和不穩定：
a.冒泡排序（Bubble sort），插入排序（Insrtion sort），歸并排序（Merge sort）和計數排序（Counting sort）等本身就具有穩定排序的特質
b.快速排序、堆排序等是不穩定排序
c.雖然很多算法本身具有穩定或不穩定排序性質但是任何排序只要稍作修改就可以修改穩定性，例如在冒泡排序中判斷交換順序的依據是if(a>b)只要變成if(a>=b)就可以破壞穩定性
二、插入排序
特點：
1,經過幾次排序后,前幾個元素就已經有序了,后序元素是否有序無關
2,怕新元素是前面已經有序元素的最小值
3.如果待排序的元素，已經有序，只有極個別的元素是無序,插入速度較快
4.如果元素是鏈式存儲，非常時候插入排序
三、代碼實現
1.頭文件中的接口
//
// Created by 27893 on 2025/8/9.
//#ifndef INSERTSORT_H
#define INSERTSORT_H
typedef struct {int key;void*data;
}Element;typedef struct {Element*data;int len;
}SortTable;void insertSort(SortTable*table);
#endif //INSERTSORT_H
2.算法的實現
//
// Created by 27893 on 2025/8/9.
//#include "InsertSort.h"void insertSort(SortTable *table) {//從第二個開始插入for (int i=1;i<table->len;i++) {if (table->data[i].key<table->data[i-1].key) {//用j來輔助查找元素的真正待插入位置int temp=table->data[i].key;int j=i-1;//只要待插入元素比j指向位置還小就往前while (j!=-1&&temp<table->data[j].key) {table->data[j+1].key=table->data[j].key;j--;}//否則結束插入到j的后一個位置table->data[j+1].key=temp;}}
}
四、希爾排序
1.希爾排序說明
在插入排序中，我們可能會遇到一個很小的數到很后面才發現，這樣就要和前面有序區的很多元素進行比較,時間復雜度接近O(n^2)
而希爾排序是將每次步長調大一點，剛開始一般為數組長度的一半，比如下面的表元素個數為10，我們第一次排序就拿當前元素與當前元素后面的第5個進行比較，這樣的比較進行5次
第二次我們步長為上次的一半，每次和自己后面的第2個進行比較，這樣的比較進行兩次
直到步長為0，結束我們的循環，這樣時間復雜度最多為O(nlog_2n)
2.希爾排序代碼
void shellSort(SortTable *table) {for (int gap=table->len/2;gap>0;gap/=2) {for (int i=gap;i<table->len;i++) {Element temp=table->data[i];int j;for (j=i;j>=gap&&temp.key<table->data[j-gap].key;j-=gap) {table->data[j]=table->data[j-gap];}table->data[j]=temp;}}
}
