Java复习——排序

r囧r小猫 2022-02-28 12:14 166阅读 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);
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bnNoaW5lX3JlYnJpdGg_size_16_color_FFFFFF_t_70]: /images/20220228/99fde872c8574dfa9b24d0319df7dceb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bnNoaW5lX3JlYnJpdGg_size_16_color_FFFFFF_t_70 1]: /images/20220228/4fefb660c0a24f8785c3ed3ad4d656f7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bnNoaW5lX3JlYnJpdGg_size_16_color_FFFFFF_t_70 2]: /images/20220228/963fc6d93b3d458992f531faa58be048.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bnNoaW5lX3JlYnJpdGg_size_16_color_FFFFFF_t_70 3]: /images/20220228/a2c74d346cec4711a4ac35e00ac84f75.png