Java复习——排序-蒲公英云

Java复习——排序

r囧r小猫 2022-02-28 12:14 204阅读 0赞

一、冒泡排序

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bnNoaW5lX3JlYnJpdGg_size_16_color_FFFFFF_t_70

package test;
/**
 * 测试冒泡排序
 * @author 凡心所向，素履以往，生如逆旅，一苇一航
 *
 */
public class maopao {
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int a[] = {0,3,5,7,2,1,4,8,9,6};
        int temp = 0;
        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]) {
                    temp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = temp;
                }
            }
        }
        //打印结果
        for(int i = 0;i<a.length;i++) {
            System.out.println(a[i]);
        }
    }
}

二、选择排序

选择排序：第一次从 R[0] ~ R[n-1] 中选取最小值，与 R[0] 进行交换，第二次从 R[1] ~ R[n-1] 中选择最小值与R[1]交换 ………,总共通过 n-1 次，得到一个安排序码从小到大的有序序码。

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bnNoaW5lX3JlYnJpdGg_size_16_color_FFFFFF_t_70 1

package test;
public class xuanze {
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int a[] = {0,3,5,7,2,1,4,8,9,6};
        int min_index,min;
        int temp = 0;
        for(int i = 0 ; i < a.length-1 ; i++) {
            min_index = i;
            min = a[i];
            for(int j=i+1;j<a.length;j++) {
                if(a[j]<min) {
                    min = a[j];
                    min_index = j;
                }
            }
            temp = a[i];
            a[i] = a[min_index];
            a[min_index] = temp;
        }
        for(int i=0 ;i<a.length;i++) {
            System.out.println(a[i]);
        }
    }
}

三、插入排序

插入排序分为三种：1、插入排序法；2、谢尔排序法；3、二叉树排序法

插入排序的基本思想：把n个待排序的元素看成是一个有序表和一个无序表，开始有序表只包含一个元素，无序表包含n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序码进行比较，把它插入到有序表的适当位置，使之成为新的有序表。

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bnNoaW5lX3JlYnJpdGg_size_16_color_FFFFFF_t_70 2

package paixu;
/**
 * 插入排序
 * @author 凡心所向，素履以往，生如逆旅，一苇一航
 *
 */
public class charu {
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int a[] = {0,3,1,6,8,2,4,9,7,5};
        for(int i=1;i<a.length;i++) {
            int insertVal = a[i];
            int index = i-1;
            while(index>=0&&insertVal<a[index]){
                a[index+1] = a[index];
                index--;
            }
            a[index+1] = insertVal;
        }
        //输出结果
        for(int i = 0;i<a.length;i++) {
            System.out.println(a[i]);
        }
    }
}

四、快速排序

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bnNoaW5lX3JlYnJpdGg_size_16_color_FFFFFF_t_70 3

package paixu;
/**
 * 测试快速排序
 * @author 凡心所向，素履以往，生如逆旅，一苇一航
 *
 */
public class kuaisu {
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int a[] = {0,3,6,8,1,4,2,5,7,9};
        QuickSort qs = new QuickSort();
        qs.kuaiSu(0, a.length-1, a);
        //输出结果
        for(int i=0;i<a.length;i++) {
            System.out.println(a[i]);
        }
    }
}
//快速排序
class QuickSort{
    public void kuaiSu(int left,int right,int []a) {
        int l = left;
        int r = right;
        int privot = a[(left+right)/2];
        int temp = 0;
        while(l<r) {
            while(a[l]<privot) l++;
            while(a[r]>privot) r--;
            if(l>=r) break;
            temp = a[l];
            a[l] = a[r];
            a[r] = temp;
            if(a[l]==privot) --r;
            if(a[r]==privot) ++l;
        }
        if(l==r) {
            l++;
            r--;
        }
        if(left<r) kuaiSu(left,r,a);
        if(right>l) kuaiSu(l,right,a);
    }
}