1、概念
image.png
2定枷、內(nèi)排序與外排序
內(nèi)排序是在排序整個過程中孤澎，待排序的所有記錄全部被放置在內(nèi)存中。外排序是由于排序的記錄個數(shù)太多欠窒，不能同時放置在內(nèi)存覆旭，整個排序過程需要在內(nèi)外存之間多次交換數(shù)據(jù)才能進行。
排序算法的性能主要受3哥方面影響：
1岖妄、時間性能 2型将、輔助空間 3、算法的復(fù)雜性
簡單選擇排序算法
就是通過n-i次關(guān)鍵字間的比較荐虐，從n-i+1個記錄中選出關(guān)鍵字最小的記錄七兜，并和第i個記錄交換之
/* 對順序表L作簡單選擇排序 */
void SelectSort(SqList *L)
{
int i,j,min;
for(i=1;i<L->length;i++)
{
min = i; /* 將當前下標定義為最小值下標 */
for (j = i+1;j<=L->length;j++)/* 循環(huán)之后的數(shù)據(jù) */
{
if (L->r[min]>L->r[j]) /* 如果有小于當前最小值的關(guān)鍵字 */
min = j; /* 將此關(guān)鍵字的下標賦值給min */
}
if(i!=min) /* 若min不等于i，說明找到最小值福扬，交換 */
swap(L,i,min); /* 交換L->r[i]與L->r[min]的值 */
}
}
簡單選擇排序復(fù)雜度O(n^2)
直接插入排序
直接插入排序的基本操作是將一個記錄插入到已經(jīng)排好序的有序表中腕铸，從而得到一個新的、記錄數(shù)增1的有序表铛碑。
/* 對順序表L作直接插入排序 */
void InsertSort(SqList *L)
{
int i,j;
for(i=2;i<=L->length;i++)
{
if (L->r[i]<L->r[i-1]) /* 需將L->r[i]插入有序子表 */
{
L->r[0]=L->r[i]; /* 設(shè)置哨兵 */
for(j=i-1;L->r[j]>L->r[0];j--)
L->r[j+1]=L->r[j]; /* 記錄后移 */
L->r[j+1]=L->r[0]; /* 插入到正確位置 */
}
}
}
直接插入排序法的時間復(fù)雜度為O(n^2)狠裹，同樣的時間復(fù)雜度，直接插入排序法比冒泡和簡單選擇排序的性能要好一些汽烦。
希爾排序
/* 對順序表L作希爾排序 */
void ShellSort(SqList *L)
{
int i,j,k=0;
int increment=L->length;
do
{
increment=increment/3+1;/* 增量序列 */
for(i=increment+1;i<=L->length;i++)
{
if (L->r[i]<L->r[i-increment])/* 需將L->r[i]插入有序增量子表 */
{
L->r[0]=L->r[i]; /* 暫存在L->r[0] */
for(j=i-increment;j>0 && L->r[0]<L->r[j];j-=increment)
L->r[j+increment]=L->r[j]; /* 記錄后移涛菠，查找插入位置 */
L->r[j+increment]=L->r[0]; /* 插入 */
}
}
printf(" 第%d趟排序結(jié)果: ",++k);
print(*L);
}
while(increment>1);
}
