首页 > 代码库 > 算法整理(三):插入排序
算法整理(三):插入排序
插入排序很简单,就像打扑克。手里有个牌4,再来一张牌5就本能的放到第一个牌的右边。如果来了个3就从右往左扫描,只要左边的比这个待插入数字大就交换。
插入排序是一种稳定的排序方法,时间复杂度O(n*n),空间复杂度O(1),最好的情况下时间复杂度为O(1).即本来就是一个有序或者相等的数组,则只需比较n-1次即可。下为源码,只需三行代码即可。
//============================================================================ // Name : QuikSort.cpp // Author : YanZi // Version : // Copyright : Your copyright notice // Description : Hello World in C++, Ansi-style //============================================================================ #include <iostream> #include <malloc.h> using namespace std; void swap1(int a, int b); void printArray(int* in, int n); void quickSort1(int* x, int l, int r);//双边扫描,快速排序 void quickSort2(int x[], int l, int r);//单边扫描,快速排序 void swap2(int &a,int &b); //交换,在MinGW上必须采用此方法,swap1无效 #define N 8 //数组的长度 int main() { int* input = NULL; input = (int*)malloc(N * sizeof(int)); if(input == NULL){ cout<<"内存溢出"<<endl; } for(int i = 0; i < N; i++){ input[i] = rand(); } // int input[] = {55, 41, 59, 26, 53, 58, 97, 93}; cout<<"原始数据:"<<endl; printArray(input, N); quickSort2(input, 0, N-1); printArray(input, N); return 0; } void swap1(int a, int b){ int temp = a; a = b; b = temp; } void printArray(int * in, int n){ if(in == NULL){ return; } for(int i = 0; i<n; i++){ cout<<" "<<in[i]; } cout<<endl; } void quickSort1(int* x, int l, int r){ if(l < r){ int i = l, j = r, key = x[l]; while(i < j){ while( i < j && x[j] >= key){ j--; } if(i < j){ x[i++] = x[j]; } while(i < j && x[i] <= key){ i++; } if(i < j){ x[j--] = x[i]; } } cout<<"i = " <<i<<" j = "<<j<<endl; x[i] = key; quickSort1(x, l, i-1); quickSort1(x, i+1, r); } } void quickSort2(int x[], int l, int r){ if(l >= r) return; int m = l; for(int i = l + l; i <= r; i++ ){ if(x[i] < x[l]){ swap2(x[++m], x[i]); } } swap2(x[l], x[m]); quickSort2(x, l, m - 1); quickSort2(x, m + 1, r); } void swap2(int &a,int &b){ if(a==b) return;//对同一地址的数据交换,会使其结果为0 a=a^b; b=a^b; a=a^b; }
插入排序的一大特点:非常适合一个基本有序的数组,进行精确排序。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。