数据结构&算法（一）

一、Java实现快速排序算法

package test;

public class FastSort {
    public static void main(String[] args) {
        System.out.println("*********快速排序***********");
        int[] a = new int[8];
        System.out.println("随机产生测试用的8个数据：");
        //产生数据
        for(int i=0;i<8;i++) {
            int r = (int)(Math.random()*100)+1;  //产生1-100的随机数
            a[i] = r;   //放在一个数组
            if(i==7) {
                System.out.print(a[i]);
            }else {
                System.out.print(a[i]+",");
            }       
        }
        System.out.println();
        int start = 0;
        int end = a.length-1;
        sort(a,start,end);
        System.out.println("快速排序好的数据：");
        //输出排序结果
        for(int i=0;i<a.length;i++) {
            if(i==7) {
                System.out.print(a[i]);
            }else {
                System.out.print(a[i]+",");
            }
        }
        
    }
    //快速排序
    public static void sort(int[] a,int left,int right) {
        int start = left;
        int end = right;
        int center = a[left];
        //逐轮排序，一轮下来就确定了中心枢纽，左边都比中心枢纽值小，右边都比中心枢纽值大
        while(start<end) {
            //从后往前排
            while(start<end && a[end]>=center) {
                end--;
            }
            if(a[end]<=center) {
                int temp = a[end];
                a[end] = a[start];
                a[start] = temp;
            }
            //从前往后排
            while(start<end && a[start]<=center) {
                start++;
            }
            if(a[start]>=center) {
                int temp = a[start];
                a[start] = a[end];
                a[end] = temp;
            }
        }
        //递归
        if(start>left)//左边序列
            sort(a,left,start-1);
        if(end<right)//右边序列
            sort(a,end+1,right);
    }
}

图片.png

二、Java实现折半插入排序算法

package test;

public class BinaryInsertSort {
    public static void main(String[] args) {
        System.out.println("*********折半插入排序***********");
        int[] a = new int[8];
        System.out.println("随机产生测试用的8个数据：");
        //产生数据
        for(int i=0;i<8;i++) {
            int r = (int)(Math.random()*100+1);
            a[i] = r;
            if(i==7) {
                System.out.print(a[i]);
            }else {
                System.out.print(a[i]+",");
            }
        }
        System.out.println();
        sort(a);
        System.out.println("输出排好序的数据");
        for(int j=0;j<8;j++) {
            if(j==7) {
                System.out.print(a[j]);
            }else {
                System.out.print(a[j]+",");
            }
        }
    }
    //折半插入排序
    public static void sort(int[] a) {
        int n = a.length;
        int i,j;
        for(i=1;i<n;i++) {
            int low = 0;
            int high = i-1;
            int temp = a[i];
            //使用二分法寻找temp插入有序序列的正确位置
            while(low<=high) {
                int center = (low+high)/2;
                //移动low，high的位置
                if(a[center]<temp) {
                    low = center+1;
                }else {
                    high = center-1;
                }
            }
            //把temp的正确位置后面元素后移一位
            for(j=i-1;j>=low;j--) {
                a[j+1] = a[j];
            }
            //插入temp
            a[low] = temp;
        }
    }
}

图片.png

三、Java实现冒泡排序算法

package test;

public class BubbleSort {
    public static void main(String[] args) {
        System.out.println("*********冒泡排序***********");
        int[] a = new int[8];
        System.out.println("随机产生测试用的8个数据：");
        //产生数据
        for(int i=0;i<8;i++) {
            int r = (int)(Math.random()*100)+1;  //产生1-100的随机数
            a[i] = r;   //放在一个数组
            if(i==7) {
                System.out.print(a[i]);
            }else {
                System.out.print(a[i]+",");
            }       
        }
        System.out.println();
        sort(a);
        System.out.println("快速排序好的数据：");
        //输出排序结果
        for(int i=0;i<a.length;i++) {
            if(i==7) {
                System.out.print(a[i]);
            }else {
                System.out.print(a[i]+",");
            }
        }
    }
    //冒泡排序
    public static void sort(int[] a) {
        //外层循环控制排序趟数
        for(int i=0;i<a.length-1;i++) {
            //内层循环控制每一趟比较多少次
            for(int j=0;j<a.length-1-i;j++) {
                //如果后一个比前一个元素大，则往后冒
                if(a[j]>a[j+1]) {
                    //两两交换
                    int temp = a[j+1];
                    a[j+1] = a[j];
                    a[j] = temp;
                }
            }
        }
    }
}

图片.png