插入类排序：

（一）思想：在一个已经排好序的序列中，将未被排进的元素按照原先的规定插入到指定位置。

（二）分类：

1、直接插入排序：

①思想：最基本的插入排序，将第i个插入到前i-1个中的适当位置。

②时间复杂度：T(n) = O(n²)。

③空间复杂度：S(n) = O(1)。

④稳定性：稳定排序。循环条件while(r[0].key < r[j].key)保证的。

⑤程序：

void InsSort(RecordType r[], int length)

{

for(i = 2; I <= length; i++)

{

r[0] = r[i];

j = i – 1;

while(r[0].key < r[j].key)

{

r[j + 1] = r[j]; j = j – 1;

}

r[j+1] = r[0];

}

}

2、折半插入排序：

①思想：因为是已经确定了前部分是有序序列，所以在查找插入位置的时候可以用折半查找的方法进行查找，提高效率。

②时间复杂度：比较时的时间减为O(n㏒n)，但是移动元素的时间耗费未变，所以总是得时间复杂度还是O(n²)。

③空间复杂度：S(n) = O(1)。

④稳定性：稳定排序。

⑤程序：

void BinSort(RecordType r[], int length)

{

for(i = 2; i <= length; i++)

{

x = r[i];

low = 1; high = i – 1;

while(low <= high)

{

mid = (low + high) / 2;

if(x.key < r[mid].key)

high = mid – 1;

else

low = mid – 1;

}

for(j = i – 1; j >= low; --j)

r[j + 1] = r[j];

r[low] = x;

}

}

3、希尔排序：

①思想：又称缩小增量排序法。把待排序序列分成若干较小的子序列，然后逐个使用直接插入排序法排序，最后再对一个较为有序的序列进行一次排序，主要是为了减少移动的次数，提高效率。原理应该就是从无序到渐渐有序，要比直接从无序到有序移动的次数会少一些。

②时间复杂度：O(n的1.5次方)

③空间复杂度：O(1)

④稳定性：不稳定排序。{2,4,1,2}，2和1一组4和2一组，进行希尔排序，第一个2和最后一个2会发生位置上的变化。

⑤程序：

void ShellInsert(RecordType r[], int length, int delta)

{

for(i = 1 + delta; i <= length; i++)/*1+delta为第一个子序列的第二个元素的下表*/

if(r[i].key < r[1 - delta].key)

{

r[0] = r[i];

for(j = i – delta; j > 0 && r[0].key < r[j].key; j -=delta)

r[j + delta] = r[j];

r[j + delta] = r[0];

}

}

void ShellSort(RecordType r[], int length, int delta[], int n)

{

for(i = 0; i <= n – 1; ++i)

ShellInsert(r, length, delta[i]);

}

交换类排序：

（一）思想：通过交换逆序元素进行排序的方法。

（二）分类：

1、冒泡排序：

①思想：反复扫描待排序序列，在扫描的过程中顺次比较相邻的两个元素的大小，若逆序就交换位置。第一趟，从第一个数据开始，比较相邻的两个数据，（以升序为例）如果大就交换，得到一个最大数据在末尾；然后进行第二趟，只扫描前n-1个元素，得到次大的放在倒数第二位。以此类推，最后得到升序序列。如果在扫描过程中，发现没有交换，说明已经排好序列，直接终止扫描。所以最多进行n-1趟扫描。

②时间复杂度：T(n) = O(n²)。

③空间复杂度：S(n) = O(1)。

④稳定性：稳定排序。

⑤程序：

void BubbleSort(RecordType r[], int length)

{

n = length;

change = TRUE;

for(i = 1; i <= n – 1 && change; i++)

{

change = FALSE;

for(j = 1; j <= n – I; ++j)

if(r[j].key > r[j + 1].key)

{

x = r[j];

r[j] = r[j + 1];

r[j + 1] = x;

change = TRUE;

}

}

}

2、快速排序：

①思想：冒泡排序一次只能消除一个逆序，为了能一次消除多个逆序，采用快速排序。以一个关键字为轴，从左从右依次与其进行对比，然后交换，第一趟结束后，可以把序列分为两个子序列，然后再分段进行快速排序，达到高效。

②时间复杂度：平均T(n) = O(n㏒n)，最坏O(n²)。

③空间复杂度：S(n) = O(㏒n)。

④稳定性：不稳定排序。{3， 2， 2}

⑤程序：

void QKSort(RecordType r[], int low, int high)

{

int pos;

if(low < high)

{

pos = QKPass(r, low, high);

QKSort(r, low, pos - 1);

QKSort(r, pos + 1, high);

}

}

int QKPass(RecordType r[], int left, int right)

{

RecordType x;

int low, high;

x = r[left];

low = left;

high = right;

while(low < high)

{

while(low < high && r[high].key >= x.key)

high--;

if(low < high)

{

r[low] = r[high];

low++;

}

while(low < high && r[low].key < x.key)

low++;

if(low < high)

{

r[high] = r[low];

high--;

}

}

r[low] = x;

return low;

}

选择类排序：

（一）思想：每一趟在n – i + 1 ( i = 1,2, … , n - 1)个记录中选取关键字最小的记录作为有序序列中的第i个记录。

（二）分类：

1、简单选择排序：

①思想：第一趟时，从第一个记录开始，通过n – 1次关键字的比较，从n个记录中选出关键字最小的记录，并和第一个记录进行交换。第二趟从第二个记录开始，选择最小的和第二个记录交换。以此类推，直至全部排序完毕。

②时间复杂度：T(n) = O(n²)。

③空间复杂度：S(n) = O(1)。

④稳定性：不稳定排序，{3， 3， 2}。

⑤程序：

void SelectSort(RecordType r[], int length)

{

n = length;

for(i = 1; i <= n - 1; i++)

{

k = i;

for(j = i + 1; j <= n; i++)

if(r[j].key < r[k],key)

k = j;

if(k != i)

{

x = r[i];

r[i] = r[k];

r[k] = x;

}

}

}