插入排序
文章转自王牌软件
站长推荐:NSetup一键部署软件
一键式完成美化安装包制作，自动增量升级，数据统计，数字签名。应对各种复杂场景，脚本模块化拆分，常规复杂的脚本代码，图形化设置。无需专业的研发经验，轻松完成项目部署。(www.nsetup.cn)
只回答业务咨询
站长推荐:NSetup一键部署软件
一键式完成美化安装包制作，自动增量升级，数据统计，数字签名。应对各种复杂场景，脚本模块化拆分，常规复杂的脚本代码，图形化设置。无需专业的研发经验，轻松完成项目部署。(www.nsetup.cn)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 |
#include <iostream> #include <algorithm> using namespace std; void insert(int a[], int len) { /* 1.从第二个开始，把第二个抽出来当临时变量，这时假设这个位置是空的 2.当左边的数据比这个临时变量大时，将左边的数值向右移动， 直到遇到左边，直到左边的数据小于这个临时变量为止 3.将这个临时变量插入到这个空位置上 排序数组：5 7 4 2 6 第一次 temp = 7 5 0 4 2 6--》左边的比这个临时变量小，且已经到达了最左端 5 7 4 2 6（结束） 第二次 temp = 4 5 7 0 2 6 5 5 7 2 6 5 5 7 2 6 4 5 7 2 6 (结束) 第三次 temp = 2 4 5 7 7 6 4 5 5 7 6 4 4 5 7 6 2 4 5 7 6 (结束) 第四次 temp = 6 2 4 5 7 7 2 4 5 6 7 (结束) 因为左边的5比6小，所以就停止将左边的数据右移了，将临时变量插入到这里 */ for (int i=1; i<len; i++) { cout<<"第"<<i<<"次排序："<<endl; int temp = a[i]; //定义临时变量 cout<<"temp = "<<temp<<endl; int j; //当 (j>0) 遇到最左端时，或者，(a[j-1] > temp) 左边的数据比这个临时变量小时，停止 for (j=i; j>0&&a[j-1]>temp; j--) { a[j] = a[j-1];//将左边的数值向右移到右边 //循环输出，看看排序经过 for (int y=0; y<len; y++) { cout<<a[y]<<" "; } cout<<endl; } cout<<"要插入的位置 j = "<<j<<endl; cout<<"要插入的位置上的值 a[j] = "<<a[j]<<endl; a[j] = temp; //将这个临时变量插入到这个空位上 //循环输出，看看排序经过 cout<<"第"<<i<<"次排序后的结果："<<endl; for (int k=0; k<len; k++) { cout<<a[k]<<" "; } cout<<endl<<endl; } } void show(int a[], int len) { for (int i=0; i<len; i++) { cout<<a[i]<<" "; } cout<<endl; } int main() { int a[5] = {5,7,4,2,6}; cout<<"插入排序："<<endl; cout<<"排序前："<<endl; show(a, 5); cout<<endl; insert(a, 5); cout<<endl; cout<<"排序后："<<endl; show(a, 5); return 0; } |
插入排序InsertionSort，参数是一个数组包含了n个待排序的数，输入的各个数字是原地排序的（sorted in place），意即这些数字就是在数组A中进行重新排序的，在任何时刻，至多只有其中的常数个数字是存储在数组之外的，当过程InsertionSort执行完毕后，输入数组A中就包含了已排好序的数组输出序列。
下面是利用C++语言实现的插入排序代码:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
#include <iostream> #define N 10 using namespace std; //声明插入排序函数 int* insertionSort(int *array,int length); int main() { int array[N] = {2,1,3,67,35,12,9,7,45,0}; insertionSort(array,N); for(int i=0;i<N;i++) { cout<<array[i]<<endl; } return 0; } int * insertionSort(int * array,int length) { for(int i=1;i<length;i++) { int key = array[i]; int j = i-1; while(j>=0 && array[j]>key)//注意j的取值>=0 { array[j+1] = array[j]; j=j-1; }//while array[j+1] = key; }//for return array; } |
插入排序的算法复杂性分析：对于插入排序，它的复杂性依赖于待排序数组的一些属性，待排序数组长度、已排好序程度等。我们一般考察最坏情况下即逆序排序和最佳情况下即已排好序的复杂性。
最佳情况下：此时待排序数组已经是一个排好序的数组，推理可得程序运行时间可以表示为an+b；因此，它是n的一个线性函数。
最坏情况下：此时待排序数组是一个逆序数组，此时，我们必须把每个元素array[i]与整个已排序的子数组array[1...i-1]中的每个元素进行比较，因而，最坏情况下程序的运行 时间为an^2+bn+c，这是一个关于n的二次函数。
一般来说，如同插入排序一样，一个算法的运行时间对某一给定的输入来说，往往是固定的。
王牌软件，兼职软件设计，软件修改，毕业设计。
本文出自 王牌软件，转载时请注明出处及相应链接。
本文永久链接: http://www.softwareace.cn/?p=169
