数据结构与算法（C/C++版）【排序】

第八章《排序》

 一、直接插入排序 

//直接插入排序 //算法思想：每趟将一个待排的关键字按照其值的大小插入到已经排好的部分有序序列的适当位置上，直到所有待排关键字都***入到有序序列中为止。

 //（1）时间复杂度分析：
 // 　　　　　　 ①最坏情况（整个序列逆序）：O(n²)
 // 　　　　　　 ②***情况（整个序列有序）：O(n)
 // 　　　　　　 ③平均时间复杂度：O(n²)
 //（2）空间复杂度分析：
 // 　　　　　　 ①：O(1)

void InsertSort(int R[], int n) //待排关键字存储在R[]中，默认为整型，个数为n { int i,j; int temp; for(int i= 1; i<n; i++) //无序列表中挑选元素 { temp=R[i]; //将带插入关键字暂存于temp中 j=i-1; while(j>0 && temp < R[j]) //循环完成从待排关键字之前的关键字开始扫描，如果大于待排关键字，则后移一位 { R[j+1] = R[j]; --j; } R[j+1] = temp; //将temp中暂存的待排关键字插入到正确位置 } }