排序（模版+代码） - JAVA

插入排序：

有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法――插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外，而第二部分就只包含这一个元素。在第一部分排序后，再把这个最后元素插入到此刻已是有序的第一部分里的位置。

//Insertion_sort
#include
  
   
#include
   
     using namespace std; int main() { int a[10],i; for(i=1;i<10;i++) a[i]=1+rand()%100;//随机生成一些整数 //Insert_sort for(i=2;i<10;i++) { // 将a[i] insert the sequence a[i-1]....a[1] int key=a[i]; int j=i-1; while(j>0&&a[j]>key) { a[j+1]=a[j]; j--; } a[j+1]=key; } //printf the result for(i=1;i<10;i++) { cout<
    
     
 选择排序： 
      
      每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。
 





 
       
     //Selection_insert
#include
      
       
#include
       
         using namespace std; int main() { int a[10],i,j,key,temp,k; //随机生成9个数 for(i=1;i<=9;i++) { a[i]=1+rand()%100; } //Selection_insert for(i=1;i<=9;i++) { //slect the smallest number from the sequence key=a[i]; for(j=i+1;j<=9;j++) { if(a[j]
        
         合并排序： 合并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。合并排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。合并排序也叫归并排序。
         //Merge_sort
#include
          
           
#include
           
             const int maxnum=999999; using namespace std; int a[50]; void merge(int *a,int p,int q,int r) { int m=q-p+1; int n=r-q; int left[100],right[100]; int i,j,k; for(i=1;i<=m;i++) { left[i]=a[i+p-1]; } for(j=1;j<=n;j++) { right[j]=a[j+q]; } left[m+1]=maxnum; right[n+1]=maxnum; i=j=1; k=p; while(k<=r) { if(left[i]<=right[j]) { a[k++]=left[i++]; } else a[k++]=right[j++]; } } void merge_sort(int *a,int p,int q) { if(p
            
             
 堆排序： n个关键字序列Kl，K2，…，Kn称为（Heap），当且仅当该序列满足如下性质（简称为堆性质）： (1)ki<=k(2i）且ki<=k(2i+1)(1≤i≤ n），当然，这是小根堆，大根堆则换成>=号。//k(i）相当于二叉树的非叶子结点，K(2i）则是左子节点，k(2i+1）是右子节点 若将此序列所存储的向量R[1..n]看做是一棵
             完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树： 
             
 
             树中任一非叶子结点的关键字均不大于（或不小于）其左右孩子（若存在）结点的关键字。 
             //HEAP_SORT
#include
              
               
#include
               
                 using namespace std; int maxv=49,a[50]; void Max_Heapify(int *a,int i) { int l=i*2,r=i*2+1,largest; if(l<=maxv&&a[l]>a[i]) largest=l; else largest=i; if(r<=maxv&&a[r]>a[largest]) largest=r; if(largest!=i) { int temp=a[i]; a[i]=a[largest]; a[largest]=temp; Max_Heapify(a,largest); } } void Build_Max_Heap(int *a) { int i; for(i=maxv/2;i>=1;i--) Max_Heapify(a,i); } void Heap_Sort(int *a) { for(int i=maxv;i>=2;i--) { int temp=a[1]; a[1]=a[i]; a[i]=temp; maxv=maxv-1; Max_Heapify(a,1); } } int main() { int i,j; for(i=1;i<50;i++) a[i]=1+rand()%99; Build_Max_Heap(a); Heap_Sort(a); for(i=1;i<=49;i++) cout<
                
                 计数排序： 计数排序是一个非基于比较的排序算法，该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。
                 
 
                  
                   
                 //Counting_Sort
#include
                  
                   
using namespace std;
int main()
{
	int a[9]={0,2,5,3,0,2,3,0,3};
	int c[6];
	int i;
	int b[9];
	for(i=0;i<=5;i++)
	c[i]=0;
	for(i=1;i<=8;i++)
	c[a[i]]=c[a[i]]+1;
	for(i=1;i<=5;i++)
	c[i]=c[i-1]+c[i];
	for(i=8;i>=1;i--)
	{
		b[c[a[i]]]=a[i];
		c[a[i]]--;
	}
	for(i=1;i<=8;i++)
	cout<
                   
                    转载请注明出处http://write.blog.csdn.net/postedit