当前位置：首页 > news >正文

Java实现排序算法(一)

news 来源：原创 2024/5/18 14:24:10

 
 /**
 * @(#)SortTest.java
 * 排序算法
 *
 * @author 
 * @version 1.00 2008/8/2
 */
public class SortTest {
    /**
     *选择排序
     *在找到全局第i小的时候记下该元素位置，最后跟第i个元素交换，从而保证数组最终的有序
    */
   void selectSort(int[] sortIn){
        int i,j,temp,min=0;
        for(i=0;i<sortIn.length;i++){
            min=i;
            for(j=i;j<sortIn.length;j++){//每一趟都选择一个最小的 
                if(sortIn[j]<sortIn[min]) min=j;
            }
            //交换 
            swap(sortIn,i,min);
        }
    }
    
    /**
     *冒泡排序
     *算法思想是每次从数组末端开始比较相邻两元素，把第i小的冒泡到数组的第i个位置
     */
    void bubbleSort(int[] sortIn){
        for(int i=0;i<sortIn.length;i++){
            for(int j=sortIn.length-1;j>i;j--){
                if(sortIn[j]<sortIn[j-1])
                    swap(sortIn,j-1,j);         
            }
        }
    }
    
    /**
     *插入排序
     */
    void insertSort(int[] sortIn){
        for(int i=1;i<sortIn.length;i++){
            int temp=sortIn[i];
            int j=i-1;
            while(j>=0&&temp<sortIn[j]){
                sortIn[j+1]=sortIn[j];//向后移动元素 
                j--;
            }
            sortIn[j+1]=temp;
        }
    }
    
    /**
     *希尔排序
     *Shell排序每次把数据分成若个小块，来使用插入排序，而且之后在这若个小块
     *排好序的情况下把它们合成大一点的小块，继续使用插入排序，不停的合并小块，
     *知道最后成一个块，并使用插入排序。
     *这里每次分成若干小块是通过“增量” 来控制的，开始时增量交大，接近N/2,
     *从而使得分割出来接近N/2个小块，逐渐的减小“增量“最终到减小到1。
     */
    void sheelSort(int[] sortIn){
        int d=sortIn.length;
        while(d>1){
            d=(d+1)/2;
            for(int i=0;i<sortIn.length-d;i++){
                if(sortIn[i+d]<sortIn[i]){
                    swap(sortIn,i+d,i);
                }
            }
        }
    }
    /**
     *快速排序
     *(1)分解(2)求解(3)组合
     */
    void quickSort(int[] sortIn,int low,int high){
        int pivotpos;//划分后的基准记录的位置 
        if(low<high){//仅当区间长度大于1时才需排序 
            pivotpos=partition(sortIn,low,high);//做划分 
            quickSort(sortIn,low,pivotpos-1);//对左区间进行递归排序 
            quickSort(sortIn,pivotpos+1,high);//对右区间进行递归排序 
        }
    }
    
    private int partition(int[] sortIn,int i,int j){
        int pivot=sortIn[i];
        while(i<j){
            //从右向左扫描，查找第一个关键字小于pivot的记录 
            while(i<j&&sortIn[j]>=pivot) j--;
            if(i<j){
                swap(sortIn,i,j);//交换sortIn[i]和sortIn[j] 
                i++;
            }
            
            //从左向右扫描，查找第一个关键字大于pivot的记录 
            while(i<j&&sortIn[i]<=pivot) i++;
            if(i<j){
                swap(sortIn,i,j);
                j--;
            }
        }
        sortIn[i]=pivot;//基准位置已被最终定位 
        return i;
    } 
        
    /**
     *交换位置
     */
    private void swap(int a[],int i,int j){
        int temp=a[i];
        a[i]=a[j];
        a[j]=temp;
    }
    
    public static void main(String[] args){
        int[] sortIn={49,38,56,97,76,13,27,99,55,3};
        SortTest ss=new SortTest();
        
        //ss.selectSort(sortIn); 
        //ss.bubbleSort(sortIn); 
        //ss.insertSort(sortIn); 
        //ss.sheelSort(sortIn); 
        ss.quickSort(sortIn,0,sortIn.length-1);
        for(int num:sortIn){
            System.out.print(" "+num);
        }
    }
}