排序算法： 基本：冒泡，快速，选择，堆，插入，shell 多路并归： 1.冒泡排序： 思想：交换排序，通过相邻的交换来达到排序的目的。 流程： 1.对数组中的各数据，依次比较相邻两个元素的大小。 2.如果前面的大，交换。经过一轮，可把最小的排好。 3.然后用同样的方法，把剩下的数据排好。最后从小到大排好相应的数据。 #include <iostream>#include <time.h>#define SIZE 10using namespace std;void BubbleSort(int *a,int len){ int temp; for(int i=0;i<len-1;i++) { for(int j=len-1;j>i;j--) { if(a[j-1]>a[j]) { temp=a[j]; a[j]=a[j-1]; a[j-1]=temp; } } cout<<i<<":"; for(int k=0;k<len;k++) { cout<<a[k]<<" "; } cout<<endl; }}int main(){ int shuzu[SIZE]; srand(time(NULL));//随机种子 for(int i=0;i<SIZE;i++) { shuzu[i]=rand()/1000+100; } cout<<"old:"; for(int i=0;i<SIZE;i++) { cout<<shuzu[i]<<" "; } cout<<endl; BubbleSort(shuzu,SIZE); cout<<"now:"; for(int i=0;i<SIZE;i++) { cout<<shuzu[i]<<" "; } cout<<endl; } 选择排序： 思路：在每一步选取最小的来重新排列。 流程: 1.首先从原始数据中选中最小的一个，和位于第一个位置的数据交换、 2.接着从剩下的n-1数据中选择次小的，与第二个位子交换。 3.这样重复，数组从小到大排列。 #include <iostream>#include <time.h>using namespace std;#define SIZE 10void SelectionSort(int *a,int len){ int temp,k; for(int i=0;i<len-1;i++) { k=i; for(int j=i+1;j<len-1;j++) { if(a[j]<a[k]) k=j; } if(k!=i)//交换 { temp=a[k]; a[k]=a[i]; a[i]=temp; } } }int main(){ int shuzu[SIZE]; srand(time(NULL)); for(int i=0;i<SIZE;i++) { shuzu[i]=rand()/1000+100; } cout<<"old:"; for(int i=0;i<SIZE;i++) { cout<<shuzu[i]<<" "; } cout<<endl; SelectionSort(shuzu,SIZE); cout<<"now:"; for(int i=0;i<SIZE;i++) { cout<<shuzu[i]<<" "; } cout<<endl;} 插入排序： 思路：通过未排序的数据逐个插入合适的位置来完成工作。 流程： 1.首先对数组的前两个数据进行从小到大排序 2.接着第3个数据插入合适的位子 3.第4个 4.重复 #include <iostream>#include <time.h>#define SIZE 10using namespace std;void InsertionSort(int *a,int len){ int temp,j,i,k; for(i=1;i<len;i++) { //temp=a[i],a[j+1]=a[j];a[j+1]=temp;就是个交换。 判断 j-- 为逻辑 temp=a[i], j=i-1; while(j>=0 && temp<a[j]) { a[j+1]=a[j]; j--; } a[j+1]=temp; }}int main(){ int arr[SIZE]; srand(time(NULL)); for(int i=0;i<SIZE;i++) { arr[i]=rand()/1000+100; } cout<<"old:"; for(int j=0;j<SIZE;j++) { cout<<arr[j]<<" "; } cout<<endl; InsertionSort(arr,SIZE); cout<<"now:"; for(int k=0;k<SIZE;k++) { cout<<arr[k]<<" "; } cout<<endl;} Shell排序：（希尔排序，缩小增量排序） 流程 1.将有n个元素的数组，分成n/2个数字序列。第一个数据和第n/2+1成一对、。。。 2.一次循环是每个序列对排好顺序 3。然后，在变为n/4 4.不断重复。 #include <iostream>#include <time.h>using namespace std;#define SIZE 10void ShellSrot(int *a,int len){ int i,j; int r,temp; for(r=len/2;r>=1;r/=2) { for(i=r;i<len;i++) { temp=a[i]; j=i-r; while(j>=0&&temp<a[j]) { a[j+r]=a[j]; j-=r; } a[j+r]=temp; } }}int main(){ int arr[SIZE]; srand(time(NULL)); for(int i=0;i<SIZE;i++) { arr[i]=rand()/1000+100; } cout<<"old:"; for(int j=0;j<SIZE;j++) { cout<<arr[j]<<" "; } cout<<endl; ShellSrot(arr,SIZE); cout<<"now:"; for(int k=0;k<SIZE;k++) { cout<<arr[k]<<" "; } cout<<endl;}
转载于:https://www.cnblogs.com/Alandre/p/3395949.html
