一、排序的分类：
稳定排序与不稳定排序：
假设 Ri = Rj ，且排序前序列中 Ri 领先于 Rj ；若在排序后的序列中 Ri 仍领先于 Rj ，则称排序方法是稳定的。
若在排序后的序列中 Rj 仍领先于 Ri ，则称排序方法是不稳定的。
例：序列 3 15 8 8 6 9若排序后得 3 6 8 8 9 15 稳定的
若排序后得 3 6 8 8 9 15 不稳定的
内排和外排：
根据排序过程中待排序记录是否全部放置在内存中，排序分为内排和外排。内部排序: 指的是待排序记录存放在计算机随机存储器中进行的排序过程。外部排序: 指的是待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。
二、排序算法的性能分析：
算法的复杂性：体现在运行该算法时的计算机所需资源的多少上，计算机资源最重要的是时间和空间（即寄存器）资源，因此复杂度分为时间和空间复杂度。
辅助空间：辅助空间是评价排序算法的一个重要指标，辅助空间是指除了存放待排序资源之外，执行算法所需要的其他存储空间。
时间复杂度：简单的说就是程序循环执行的总的次数。算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。时间复杂度常用大O符号表述，即O(f(n))。
三、按照排序过程中所依据的原则的不同可以分类为:
►插入排序
直接插入排序 希尔排序
►交换排序
冒泡排序 快速排序
►选择排序
简单选择排序 堆排序
►归并排序
►基数排序
四、直接插入排序：
稳定性：稳定时间复杂度： O(n^2)
(1)初始数据正序，总比较次数：n-1
(2)初始数据逆序，总比较次数：(n2+n-1)/2=O(n2)
(3)初始数据无序，第i趟平均比较次数(i+1)/2，总次数为：(n2+3n)/4=O(n2)
(4)可见，原始数据越趋向正序，比较次数和移动次数越少
#include <stdio.h>void InsertSort(int par_array[], int array_size){ int i, j; int temp; for (i = 1; i < array_size; i++) { temp = par_array[i]; for (j = i - 1; j >= 0; j--) { if (temp < par_array[j]) { par_array[j + 1] = par_array[j]; } else { break; } } par_array[j + 1] = temp; }}int main(){ int i = 0; int a[] = {3, 5, 2, 1, 9, 0, 6, 4, 7, 8}; int length = sizeof(a) / sizeof(a[0]); InsertSort(a, length); for (i = 0; i < length; i++) { printf("%d ", a[i]); } printf("\n"); return 0;}
