Java的几种常见排序.docx

常见的排序算法之Java代码解释 一 简要介绍 一般排序均值的是将一个已经无序的序列数据重新排列成有序的 ? 常见的排序分为： ? 1 插入类排序 ? 主要就是对于一个已经有序的序列中，插入一个新的记录。它包括：直接插入排序，折半插入排序和希尔排序 ? 2 交换类排序 ? 这类排序的核心就是每次比较都要“交换”，每一趟排序都会发生一系列的“交换”排序，但是每一趟排序都会让一个记录排序到它的最终位置上。它包括：起泡排序，快速排序 ? 3 选择类排序 ? 顾名思义，这类排序主要就是“选择”，每一趟排序都从一系列数据中选择一个最大或最小的记录，将它放置到第一个或最好一个为位置交换，只有在选择后才交换，比起交换类排序，减少了交换记录的时间。属于它的排序：简单选择排序，堆排序 ? 4 归并类排序 ? 将两个或两个以上的有序序列合并成一个新的序列 ? 5 基数排序 ? 主要基于多个关键字排序的。 ? 下面针对上面所述的算法，讲解一些常用的java代码写的算法 二 插入类排序之直接插入排序 直接插入排序,一般对于已经有序的队列排序效果好。 基本思想：每趟将一个待排序的关键字按照大小插入到已经排序好的位置上。 算法思路，从后往前先找到要插入的位置，然后所有元素向后移动，将要插入数据插入该文职即可即可。时间复杂度为O(n2),空间复杂度为O(1) package?sort.algorithm;publicclass?DirectInsertSort {publicstaticvoid?main(String[] args) {// TODO Auto-generated method stubint?data[]={2,6,10,3,9,80,1,16,27,20};int?temp,j;for(int?i=1;idata.length;i++)? ? ? ? ? ? ? ?{? ? ? ? ? ? ? ? ?temp=data[i];? ? ? ? ? ? ? ? ?j=i-1;while(j=0data[j]temp)? ? ? ? ? ? ? ? ?{? ? ? ? ? ? ? ? ? ?data[j+1]=data[j];? ? ? ? ? ? ? ? ? ?j--;? ? ? ? ? ? ? ? ?}? ? ? ? ? ? ? ? ?data[j+1]=temp;? ? ? ? ? ? ? ?}//输出排序好的数据for(int?k=0;kdata.length;k++)? ? ? ? ? ? ? ?{? ? ? ? ? ? ? ?System.out.print(data[k]+ ? ? );? ? ? ? ? ? ? ?}?}} 三?插入类排序之折半插入排序 ? 条件：在一个已经有序的队列中，插入一个新的元素 ? 折半插入排序记录的比较次数与初始序列无关 ? 思想：折半插入就是首先将队列中取最小位置low和最大位置high，然后算出中间位置mid ? 将中间位置mid与待插入的数据data进行比较， ? 如果mid大于data，则就表示插入的数据在mid的左边，high=mid-1; ? 如果mid小于data，则就表示插入的数据在mid的右边,low=mid+1 ? ?时间复杂度O(n2),空间复杂度O(1) package?sort.algorithm;//折半插入排序publicclass?HalfInsertSort {publicstaticvoid?? ?main(String[] args)?{int?data[]={2,6,10,3,9,80,1,16,27,20};//存放临时要插入的元素数据int?temp;int?low,mid,high;for(int?i=1;idata.length;i++)? ? ? ?{? ? ? ? temp=data[i];//在待插入排序的序号之前进行折半插入? ? ? ? low=0;? ? ? ? high=i-1;while(low=high)? ? ? ? {? ? ? ? ? ?mid=(low+high)/2;if(temp data[mid])? ? ? ? ? ?high = mid - 1;else//low=high的时候也就是找到了要插入的位置，//此时进入循环中，将low加1，则就是要插入的位置了? ? ? ? ? ?low = mid + 1;? ? ? ? }//找到了要插入的位置，从该位置一直到插入数据的位置之间数据向后移动?for(int?j = i; j = low + 1; j--)? ? ? ? data[j] = data