排序的稳定性
如果i==j,且i在j前面,排序完成后i仍旧在j前面则这个排序算法是稳定的，否则不稳定.
多关键字排序
先按关键字1排序，关键词1相同则按2排序。。。 n
排序中的关键操作
1、比较：任意两个数据元素通过比较操作确定先后顺序。
2、交换: 数据元素之间需要交换才能得到预期结果
对于多关键字排序，只需要在比较操作时同时考虑多个关键字即可!
内排序
排序过程不需要访问外存就可以完成（数据可以全部装载到内存）
外排序
待排序数据量太大，整个排序过程不能在内存完成。
排序的审判
时间性能（主要）
主要体现在比较和交换的数量
2、辅助存储空间
完成排序需要的额外存储空间
必要时可以空间换时间
3、算法的实现复杂性
过于复杂的算法会影响代码的可读性和可维护性，也可能影响排序的性能
多关键字比较示例：
MultiCompare.c
#include <stdio.h> typedef struct _tag_DataElem { char desc[20]; int key1; int key2; } DataElem; int compare1(DataElem* ld, DataElem* rd) { int ret = 0; if( ld->key1 > rd->key1 ) { ret = 1; } else if( ld->key1 == rd->key1 ) { if( ld->key2 > rd->key2 ) { ret = 1; } if( ld->key2 < rd->key2 ) { ret = -1; } } else { ret = -1; } return ret; } int compare2(DataElem* ld, DataElem* rd) { return (ld->key1*100 + ld->key2) - (rd->key1*100 + rd->key2); } int main() { DataElem d1 = {"d1", 91, 80}; DataElem d2 = {"d2", 91, 88}; printf("Compare1 %s and %s: %d ", d1.desc, d2.desc, compare1(&d1, &d2)); printf("Compare2 %s and %s: %d ", d1.desc, d2.desc, compare2(&d1, &d2)); return 0; }
选择排序：
从左往右，每地 i 趟 找出i下标后面最小的元素，然后放到 i 的位置
由于在直接选择排序中存在着不相邻元素之间的互换，因此，直接选择排序是一种不稳定的排序方法。
SelectionSort.c
#include <stdio.h> void println(int array[], int len) { int i = 0; for(i=0; i<len; i++) { printf("%d ", array[i]); } printf(" "); } void swap(int array[], int i, int j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; } void SelectionSort(int array[], int len) // O(n*n) { int i = 0; int j = 0; int k = -1; for(i=0; i<len; i++) { k = i; //最小元素下标 for(j=i; j<len; j++) { if( array[j] < array[k] ) { k = j; } } swap(array, i, k); } } int main() { int array[] = {21, 25, 49, 25, 16, 8}; int len = sizeof(array) / sizeof(*array); println(array, len); SelectionSort(array, len); println(array, len); return 0; }
插入排序
通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应的位置并插入。
直接插入排序属于稳定的排序，最坏时间复杂性为O(n^2)，空间复杂度为O(1)。
InerstionSort.c
#include <stdio.h> void println(int array[], int len) { int i = 0; for(i=0; i<len; i++) { printf("%d ", array[i]); } printf(" "); } void swap(int array[], int i, int j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; } void InertionSort(int array[], int len) // O(n*n) { int i = 0; int j = 0; int k = -1; int temp = -1; for(i=1; i<len; i++) //第一个元素是有序的 { k = i; temp = array[k]; for(j=i-1; (j>=0) && (array[j]>temp); j--) { array[j+1] = array[j]; k = j; } array[k] = temp; } } int main() { int array[] = {21, 25, 49, 25, 16, 8}; int len = sizeof(array) / sizeof(*array); println(array, len); InertionSort(array, len); println(array, len); return 0; }
冒泡排序：
从后往前，相邻的两个元素对比，如果后面比前面小，则交换位置，一趟下来则首位元素为最小元素
稳定排序
#include <stdio.h> void println(int array[], int len) { int i = 0; for(i=0; i<len; i++) { printf("%d ", array[i]); } printf(" "); } void swap(int array[], int i, int j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; } void BubbleSort(int array[], int len) // O(n*n) { int i = 0; int j = 0; int exchange = 1; for(i=0; (i<len) && exchange; i++) { exchange = 0; for(j=len-1; j>i; j--) { if( array[j] < array[j-1] ) { swap(array, j, j-1); exchange = 1; } } } } int main() { int array[] = {21, 25, 49, 25, 16, 8}; int len = sizeof(array) / sizeof(*array); println(array, len); BubbleSort(array, len); println(array, len); return 0; }