插入排序是一类排序,包括直接插入排序、折半插入排序和希尔排序。一般常说的插排就是直接插入排序。
插入排序的核心是有序区,即在排序区域首部的一些元素局部有序。
直接插入排序和选择排序都是逐个将无序区的元素放到有序区,但是元素的选取(以及对应安放策略)不一样。
直接插入排序的策略是选取无序区的第一个元素,由于最前面是有序区,所以就是最后一个局部有序元素后面那个被选取。然后拿这个从有序区最后一个元素开始向前比较找到合适的位置插入。
选择排序是选取无序区最值放到无序区最左边(也就是和有序区挨着的那个)作为新的有序区的元素,如果是选择最大的放到无序区最左边,则会使整个序列是从小到大排列的。
直接插入排序直接插入排序代码如下:
#define DataType int
void insertSort(DataType* arr, int length){
int i, j, temp;
for(i = 1; i < length; i++){
temp = arr[i];
j = i - 1;
for(; j >= 0 && temp < arr[j]; --j){
// 待排序元素左侧大于它的右移
arr[j + 1] = arr[j];
}
arr[j + 1] = temp;
}
}
折半插入排序就是在直接插入排序的基础上,对有序区的遍历采用折半查找的思路。
折半插入排序折半插入排序代码如下所示
#define DataType int
void binInsertSort(DataType* arr, int length){
int i, j, low, high, mid;
DataType temp;
for(i = 1; i < length; ++i){
if(arr[i] < arr[i - 1]){
temp = arr[i];
low = 0;
high = i - 1;
while(low <= high){
mid = (low + high) / 2;
if(temp < arr[mid]){
high = mid - 1;
}
else{
low = mid + 1;
}
}
for(j = i - 1; j >= high + 1; --j){
arr[j + 1] = arr[j];
}
arr[high + 1] = temp;
}
}
}
希尔排序
随便看一篇讲十大排序的文章就会发现,希尔排序是其中一种,插入排序也是其中一种。可是为什么要把希尔排序放到插入排序底下说呢?
希尔排序本质上用的就是分组插入方法,该方法又称递减增量排序算法。
可以理解为是对插入排序的一种改进。
既然说是改进就得看插入排序有什么需要改进的地方:每次只能移动一位数据。
#define DataType int
void shellSort(DataType* arr, int length){
int i, j, d;
DataType temp;
d = length / 2;
while(d > 0){
for(i = d; i < length; ++i){
temp = arr[i];
j = i - d;
while(j >= 0 && temp < arr[j]){
arr[j + d] = arr[j];
j = j - d;
}
arr[j + d] = temp;
}
d = d / 2;
}
}
选择排序
直接选择排序
#define DataType int
// Max比较策略
bool Max(DataType x, DataType y){
return x>y?true:false;
}
void selectSort(DataType* arr, int length, bool (*p)(DataType, DataType)){
DataType temp;
int minIndex;
for(int i = 0; i < length; ++i){
//i之前的都是有序的,i是即将有序的
minIndex = i;
temp = arr[i];
for(int j = i + 1; j < length; ++j){
if(p(temp,arr[j])){
//temp始终是最小的
temp = arr[j];
minIndex = j;
}
}
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
堆排序
11
交换排序 冒泡排序基础的冒泡排序如下
#define DataType int
void bubbleSort(DataType* arr, int n){
int i, j;
for(i = 0; i < n; ++i){
for(j = n - 1; j > i; --j){
if(arr[j] < arr[j - 1]){
swap(arr[j], arr[j - 1]);
}
}
}
}
进一步地如果某趟扫描没有发生任何交换则可以判断全部有序。改进版如下:
#define DataType int
void bubbleSort(DataType* arr, int n){
int i, j;
bool sorted = false;
for(i = 0; i < n; ++i){
sorted = true;//假定已经有序
for(j = n - 1; j > i; --j){
if(arr[j] < arr[j - 1]){
swap(arr[j], arr[j - 1]);
sorted = false;
}
}
if(sorted){
return;
}
}
}
时间复杂度 O ( n 2 ) O(n^2) O(n2)
属于就地排序算法,空间复杂度 O ( 1 ) O(1) O(1)
是稳定排序
快速排序快速排序是由从冒泡排序算法改进来的,结合了分治与递归的思想。
为了实现冒泡排序,你需要每轮有一个基准值,在下面的程序中暂把它叫做datum
你每轮需要做的是:将大于基准值的值放在一边,小于基准值的值放在另一边
但是显而易见
多数快速排序算法里,基准值通常是当前处理序列的第一个值。
基准值的值是不变的,但是基准值的位置是变化的。
void quickSort(DataType* a,int l,int r)
{
if(l
int i=l,j=r;//ij为查找器,不用lr是因为结尾需要lr的值递归
DataType datum=a[l];//datum保存基准值
while(i
while(idatum)--j;//右起向左寻小于datum的数,结束条件是查找器i=j或者找到a[j]
if(idatum需要给右边
while(i
其中l和r是排序的下标范围


![[算法笔记]排序算法1:插入、选择和交换排序 [算法笔记]排序算法1:插入、选择和交换排序](http://www.mshxw.com/aiimages/31/943563.png)
