学步园

（一）插入排序

原理是，现对数组第一个和第二个排序，这样前2个元素就是有序的了，再引入第三个元素，找到合适的位置插入。。。以此插入剩余元素。这种排序算法比起冒泡排序算法效率更高，有点类似冒泡排序的改进算法。虽然效率上比冒泡排序好，但是也是一种简单排序算法，循环次数为 1+2+3...+n-1,即n(n+1)/2, 平均情况下时间复杂度还是O(n2),n的平方。

# include<iostream.h>//插入排序，按从小到大排列<br /> int a[20]={3,6,9,9,8,15,1,5,2,19,21,13,18,14,7,33,22,0,28,16};<br /> const int n=20;<br /> void insert(){<br /> int key,i,j;<br /> for(i=1;i<n;i++){<br /> key=a[i];<br /> j=i-1;<br /> while(j>=0&&a[j]>key){<br /> a[j+1]=a[j];<br /> j--;<br /> }<br /> a[j+1]=key;<br /> }<br /> }<br /> int main(){<br /> insert();<br /> for(int i=0;i<n;i++) cout<<a[i]<<" ";<br /> cout<<endl;<br /> return 0;<br /> }</p> <p>//实现二<br /> void insert_sort(int *array, int size)<br /> {<br /> int i, j, temp;<br /> for (i=1; i<size; i++) {<br /> for (j=i, temp=array[i]; j>0&&temp<array[j-1]; j--)<br /> array[j] = array[j-1];<br /> array[j] = temp;<br /> }<br /> }<br />

（二）堆排序：

#include<iostream.h>//堆排序，按从小到大排列，包括两个部分：建堆和排序<br /> int a[21]={0,3,6,9,9,8,15,1,5,2,19,21,13,18,14,7,33,22,0,28,16};<br /> int n=20;<br /> void get_heap(int a[21],int i){<br /> int largest=i,temp;<br /> if(2*i<=n&&a[largest]<a[2*i]) largest=2*i;<br /> if(2*i+1<=n&&a[2*i+1]>a[largest]) largest=2*i+1;<br /> if(largest!=i){<br /> temp=a[i];<br /> a[i]=a[largest];<br /> a[largest]=temp;<br /> get_heap(a,largest);<br /> }<br /> }<br /> void heap_sort(int a[21]){<br /> for(int j=n/2;j>=1;j--){ //建堆,将数组变成堆数组<br /> get_heap(a,j);<br /> }<br /> int temp1;<br /> for(int k=n;k>=1;k--){ //排序<br /> temp1=a[1];<br /> a[1]=a[k];<br /> a[k]=temp1;<br /> n--;<br /> get_heap(a,1);<br /> }<br /> }<br /> int main(){<br /> heap_sort(a);<br /> for(int l=1;l<=20;l++){<br /> cout<<a[l]<<" ";<br /> }<br /> cout<<endl;<br /> return 0;<br /> }</p> <p>

（三）合并排序

# include<iostream.h>//合并排序，按从小到大排列，本质思想是递归函数<br /> int a[20]={3,6,9,9,8,15,1,5,2,19,21,13,18,14,7,33,22,0,28,16};<br /> int b[20];<br /> void merge(int a[20],int p,int q,int r){<br /> for(int i=p;i<=r;i++){<br /> b[i]=a[i];<br /> }<br /> int p1=p;<br /> int q1=q;<br /> int r1=r;<br /> for(int j=p;j<=r;j++){<br /> if(p1>q){<br /> a[j]=b[q1+1];<br /> q1++;<br /> }<br /> else if(q1+1>r){<br /> a[j]=b[p1];<br /> p1++;<br /> }<br /> else{<br /> if(b[p1]<b[q1+1]){<br /> a[j]=b[p1];<br /> p1++;<br /> }<br /> else{<br /> a[j]=b[q1+1];<br /> q1++;<br /> }<br /> }<br /> }<br /> }<br /> void merge_sort(int a[20],int p,int r){<br /> int q;<br /> if(p<r){<br /> q=(p+r)/2;<br /> merge_sort(a,p,q);<br /> merge_sort(a,q+1,r);<br /> merge(a,p,q,r);<br /> }<br /> }</p> <p>int main(){<br /> int p=0;<br /> int r=19;<br /> merge_sort(a,p,r);<br /> for(int i=0;i<20;i++) cout<<a[i]<<" ";<br /> cout<<endl;<br /> return 0;<br /> }<br />

（四）快速排序

#include<iostream.h>//快速排序，按从小到大排列，重点在划分过程，用到递归函数<br /> int a[21]={0,3,6,9,9,8,15,1,5,2,19,21,13,18,14,7,33,22,0,28,16};<br /> int partition(int a[21],int p,int r){<br /> int x=a[p];<br /> int i=p-1;<br /> int j=r+1;<br /> int temp;<br /> while(1){<br /> do{<br /> j--;<br /> }while(a[j]>x);<br /> do{<br /> i++;<br /> }while(a[i]<x);<br /> if(j>i){<br /> temp=a[i];<br /> a[i]=a[j];<br /> a[j]=temp;<br /> }<br /> else return j;<br /> }<br /> }<br /> void quicksort(int a[21],int p,int r){<br /> int q;<br /> if(p<r){<br /> q=partition(a,p,r);<br /> quicksort(a,p,q);<br /> quicksort(a,q+1,r);<br /> }<br /> }</p> <p>int main(){<br /> int p=1;<br /> int r=20;<br /> quicksort(a,p,r);<br /> for(int l=1;l<=20;l++){<br /> cout<<a[l]<<" ";<br /> }<br /> cout<<endl;<br /> return 0;<br /> }</p> <p>

（五）冒泡排序

思想是：每次将数组前N个中最大（升序）或最小（降序）的数交换到数组底部，每次数组大小N--，再进行如此操作，直到所有的数都已排序即N=1。这样循环比较的次数是（n-1）+(n-2)+(n-3)....... 约等于(n)(n+1)/2, 时间复杂度为O(n2),N的平方。

 # include<iostream.h>//冒泡排序，按从小到大排列<br /> int a[20]={3,6,9,9,8,15,1,5,2,19,21,13,18,14,7,33,22,0,28,16};<br /> const int n=20;<br /> void maopao(){<br /> int temp;<br /> for(int i=0;i<n;i++){<br /> for(int j=0;j<n-i-1;j++){<br /> if(a[j]>a[j+1]){<br /> temp=a[j];<br /> a[j]=a[j+1];<br /> a[j+1]=temp;<br /> }<br /> }<br /> }<br /> }<br /> int main(){<br /> maopao();<br /> for(int i=0;i<n;i++) cout<<a[i]<<" ";<br /> cout<<endl;<br /> return 0;<br /> }</p> <p>//实现二<br /> void bubble_sort(int *array, int size)<br /> {<br /> int i, j, temp;<br /> for (i=size-1; i>1; i--)<br /> for (j=0; j<i; j++)<br /> if (array[j] > array[j+1]) {<br /> temp = array[j+1];<br /> array[j+1] = array[j];<br /> array[j] = temp;<br /> }<br /> }<br />

（六）计数排序

#include<iostream.h>//快速排序，按从小到大排列，重点在划分过程，用到递归函数<br /> int a[21]={0,3,6,9,9,8,15,1,5,2,28,21,13,18,14,7,22,19,33,0,16};<br /> int b[21];<br /> int c[40];<br /> const int n=20;<br /> void couting_sort(int a[21],int b[20],int k){<br /> for(int i=1;i<=20;i++){<br /> c[a[i]]+=1;<br /> }<br /> for(int j=1;j<=k;j++){<br /> c[j]+=c[j-1];<br /> }<br /> for(int l=1;l<=n;l++){<br /> b[c[a[l]]]=a[l];<br /> c[a[l]]=c[a[l]]-1;<br /> }<br /> }<br /> int main(){<br /> int k=39;<br /> couting_sort(a,b,k);<br /> for(int l=1;l<=20;l++){<br /> cout<<b[l]<<" ";<br /> }<br /> cout<<endl;<br /> return 0;<br /> }</p> <p>

（七）交换排序

原理是：用第一个元素和第二个元素比较，若第一个元素大于第二个，则交换，交换后第一个元素在与第三个元素比较.....直到N个元素，然后再选择第二个元素和第三个元素比较，进行同样操作.....直到选择到N个元素。这样操作完成后数组就变为升序了。其实说白了，原理就是第一次交换，确保第一个元素是最小的，第二次交换确保第二个元素是第二小的.... 以此类推。效率也很低，循环次数(n-1)(n-2)..即O(n2), n的平方，C语言实现如下：

void change_sort(int *array, int size)<br /> {<br /> int i, j, temp;<br /> for (i=0; i<size; i++)<br /> for (j=i+1; j<size; j++)<br /> if (array[i]>array[j]){<br /> temp = array[j];<br /> array[j] = array[i];<br /> array[i] = temp;<br /> }<br /> }<br />

（八）选择排序

 //选择排序扩展<br /> /*仔细看交换排序，发现其实没必要每次发现比自己小的元素就发生交换，只要和剩下的元素中最小的那个元素交换就可以了，即选择最小的元素进行交换，那么交换排序的扩展算法，选择排序就很容易得出来了，效率略比交换排序高，整体平均效率还是N的平方，C语言实现如下：*/<br /> void select_sort(int *array, int size)<br /> {<br /> int i, j, temp, pos;<br /> for (i=0; i<size; i++) {<br /> for (j=i+1, temp=array[i], pos=i; j<size; j++)<br /> if (temp > array[j]) {<br /> temp = array[j];<br /> pos = j;<br /> }<br /> array[pos] = array[i];<br /> array[i] = temp;<br /> }<br /> }<br />

（希尔排序）

void shell_sort(int *array, int size)<br /> {<br /> int gap, i, j,temp;<br /> for (gap = size/2; gap>0; gap=(gap == 2 ?1:(int)(gap/2.2)) )<br /> for (i=gap; i<size; i++) {<br /> for (j=i,temp=array[i];j>=gap && temp < array[j-gap]; j=j-gap)<br /> array[j] = array[j-gap];<br /> array[j] = temp;<br /> }<br /> }</p> <p>