0083 选择排序、直接插入排序、希尔排序

 

 

 

 

 

 

 

 

 

 

 

 

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/*
 * 选择排序
 * 
 * 第一次从arr[0]~arr[n-1]中选取最小值，与arr[0]交换
 * 第二次从arr[1]~arr[n-1]中选取最小值，与arr[1]交换
 * 第三次从arr[2]~arr[n-1]中选取最小值，与arr[2]交换
 * .....
 * 第n-1次从arr[n-2]~arr[n-1]中选取最小值，与arr[n-2]交换
 * 总共通过n-1次交换，得到一个按排序码从小到大的有序序列
 * 
 * 选择排序过程
 * 原始：[101，34，119，1]
 * 第一次：1，34，119，101    //确定1
 * 第二次：1，34，119，101    //确定34
 * 第三次1，34，101，119    //确定101
 * 
 * 总结：
 * 1.一共有数组大小-1次循环
 * 2.循环规则：
 *         1.先假定当前数是最小数
 *         2.和后面数进行比较，如果发现比当前数更小的数，就重新确定最小数得到下标
 *         3.当遍历到数组最后时，就得到本轮最小数和小标
 *         4.交换
 */

//使用选择排序[101，34，119，1]
public class SelectSorting_ {
    public static void main(String[] args) {
        int[] arr = {101,34,119,1};
        System.out.println("排序前");
        System.out.println(Arrays.toString(arr));
        selectSort(arr);
        System.out.println("排序后");
        System.out.println(Arrays.toString(arr));
        
        //测试选择排序速度
        int[] arr2 = new int[80000];
        for(int i = 0;i < 80000;i++) {
            arr2[i] = (int)(Math.random() * 80000);
        }
        Date date1 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyy-MM-dd HH:mm:ss");
        String date1Str = simpleDateFormat.format(date1);
        System.out.println("排序前的时间=" + date1Str);
        
        selectSort(arr2);
        
        Date date2 = new Date();
        String date2Str = simpleDateFormat.format(date2);
        System.out.println("排序后的时间=" + date2Str);
    }
    
    //选择排序
    public static void selectSort(int[] arr) {
/*        //原始：[101，34，119，1]
        //第一次：1，34，119，101
        //假定最小的为arr[0]，最小值下标为0
        int minIndex = 0;
        int min = arr[0];
        
        for(int j = 0+1;j < arr.length;j++) {
            if (min > arr[j]) {//说明不是最小
                min = arr[j];//重置最小值
                minIndex = j;//重置下标 
            }
        }
        //交换
        if (minIndex != 0) {
            arr[minIndex] = arr[0];
            arr[0] = min;
        }
        System.out.println("第一次\n" + Arrays.toString(arr));//[1,34,119,101]
        
        //第二次：1，34，119，101
        //假定最小的为arr[1]，最小值下标为1
        minIndex = 1;
        min = arr[1];
        
        for(int j = 1+1;j < arr.length;j++) {
            if (min > arr[j]) {//说明不是最小
                min = arr[j];//重置最小值
                minIndex = j;//重置下标 
            }
        }
        //交换
        if (minIndex != 1) {
            arr[minIndex] = arr[1];
            arr[1] = min;
        }
        System.out.println("第二次\n" + Arrays.toString(arr));//[1,34,119,101]
    
    
        //第三次：1，34，101，119
        //假定最小的为arr[1]，最小值下标为1
        minIndex = 2;
        min = arr[2];
        
        for(int j = 2+1;j < arr.length;j++) {
            if (min > arr[j]) {//说明不是最小
                min = arr[j];//重置最小值
                minIndex = j;//重置下标 
            }
        }
        //交换
        if (minIndex != 2) {
            arr[minIndex] = arr[2];
            arr[2] = min;
        }
        System.out.println("第三次\n" + Arrays.toString(arr));//[1,34,101，119]
*/        
        for(int i = 0;i < arr.length - 1;i++) {
            int minIndex = i;
            int min = arr[i];
            
            for(int j = i+1;j < arr.length;j++) {
                if (min > arr[j]) {//说明不是最小
                    min = arr[j];//重置最小值
                    minIndex = j;//重置下标 
                }
            }
            //交换
            if (minIndex != i) {
                arr[minIndex] = arr[i];
                arr[i] = min;
            }
        }
    }    
}
 

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/*
 * 直接插入排序
 * 
 * 把n个待排序的元素看成一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含n-1个元素
 * 排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码比较
 * 将它插入到有序表的适当位置，成为新的有序表
 * 
 * 插入排序过程
 * 原始：（101），34，119，1
 * 第一次：（34，101），119，1
 * 第二次：（34，101，119），1
 * 第三次：（1，34，101，119）
 * 
 */
public class InsertionSorting_ {
    public static void main(String[] args) {
        int[] arr = {101,34,119,1};
        System.out.println("排序前");
        System.out.println(Arrays.toString(arr));
        insertSort(arr);
        System.out.println("排序后");
        System.out.println(Arrays.toString(arr));
        
        //测试插入排序的速度
        int[] arr2 = new int[80000];
        for(int i = 0;i < 80000;i++) {
            arr2[i] = (int)(Math.random() * 80000);
        }
        Date date1 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyy-MM-dd HH:mm:ss");
        String date1Str = simpleDateFormat.format(date1);
        System.out.println("排序前的时间=" + date1Str);
        
        insertSort(arr2);
        
        Date date2 = new Date();
        String date2Str = simpleDateFormat.format(date2);
        System.out.println("排序后的时间=" + date2Str);
    }
    
    //直接插入排序
    public static void insertSort(int[] arr) {
/*        //第一次：{34，101，119，1}
        //定义待插入的数
        int insertVal = arr[1];
        int insertIndex = 1 - 1;
        
        //给insertVal找到插入位置
        while(insertIndex >= 0 && insertVal < arr[insertIndex]) {//保证不越界,且待插入的数还没找到插入位置
            arr[insertIndex + 1] = arr[insertIndex];//将arr[insertIndex]后移，即把101后移==>{101，101，119，1}
            insertIndex--;
        }
        //退出循环时，插入位置找到,insertIndex + 1
        arr[insertIndex + 1] = insertVal;
        System.out.println("第一次\n" + Arrays.toString(arr));//[34,101,119,1]
    
        //第二次：{34，101，119，1}
        //定义待插入的数
        insertVal = arr[2];
        insertIndex = 2 - 1;
        
        //给insertVal找到插入位置
        while(insertIndex >= 0 && insertVal < arr[insertIndex]) {//保证不越界,且待插入的数还没找到插入位置
            arr[insertIndex + 1] = arr[insertIndex];//将arr[insertIndex]后移
            insertIndex--;
        }
        //退出循环时，插入位置找到,insertIndex + 1
        arr[insertIndex + 1] = insertVal;
        System.out.println("第二次\n" + Arrays.toString(arr));//[34,101,119,1]
        
        //第三次：{1，34，101，119}
        //定义待插入的数
        insertVal = arr[3];
        insertIndex = 3 - 1;
        
        //给insertVal找到插入位置
        while(insertIndex >= 0 && insertVal < arr[insertIndex]) {//保证不越界,且待插入的数还没找到插入位置
            arr[insertIndex + 1] = arr[insertIndex];//将arr[insertIndex]后移
            insertIndex--;
        }
        //退出循环时，插入位置找到,insertIndex + 1
        arr[insertIndex + 1] = insertVal;
        System.out.println("第三次\n" + Arrays.toString(arr));//[1,34,101,119]
*/
        for(int i = 1;i < arr.length;i++) {
            //定义待插入的数
            int insertVal = arr[i];
            int insertIndex = i - 1;
            
            //给insertVal找到插入位置
            while(insertIndex >= 0 && insertVal < arr[insertIndex]) {//保证不越界,且待插入的数还没找到插入位置
                arr[insertIndex + 1] = arr[insertIndex];//将arr[insertIndex]后移
                insertIndex--;
            }
            //退出循环时，插入位置找到,insertIndex + 1
            arr[insertIndex + 1] = insertVal;
        }
    }
}

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/* 直接插入排序可能的问题：{2，3，4，5，6，7}，插入1，需要后移6次
 * 即当需要插入的数时较小数时，后移的次数明显增多，对效率有影响
 * 
 * 希尔排序
 * 希尔排序也是一种插入排序，是直接插入排序更高效的版本，也称为缩小增量排序
 * 
 * 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序
 * 随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件被分成一组，算法终止
 * 
 * 希尔排序过程
 * 原始：8，9，1，7，2，3，5，4，6，0
 * 初始增量：length/2=5,分成5组(8,3)(9,5)(1,4)(7,6)(2,0)，进行直接插入排序
 * 结果：3,5,1,6,0,8,9,4,7,2
 * 缩小增量：5/2=2，分成2组(3,1,0,9,7)(5,6,8,4,2),进行直接插入排序
 * 结果：0,2,1,4,3,5,7,6,9,8
 * 继续缩小增量：2/2=1，分成1组，进行直接插入排序
 * 结果：0,1,2,3,4,5,6,7,8,9
 * 
 * 1.交换法
 * 2.移位法
 */
public class ShellSorting_ {
    public static void main(String[] args) {
        int[] arr = {8,9,1,7,2,3,5,4,6,0};
        System.out.println("排序前");
        System.out.println(Arrays.toString(arr));
        shellSort(arr);
        System.out.println("排序后");
        System.out.println(Arrays.toString(arr));
        
        //测试希尔排序（交换法）的速度
        int[] arr2 = new int[80000];
        for(int i = 0;i < 80000;i++) {
            arr2[i] = (int)(Math.random() * 80000);
        }
        Date date1 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyy-MM-dd HH:mm:ss");
        String date1Str = simpleDateFormat.format(date1);
        System.out.println("交换法排序前的时间=" + date1Str);
        
        shellSort(arr2);
        
        Date date2 = new Date();
        String date2Str = simpleDateFormat.format(date2);
        System.out.println("交换法排序后的时间=" + date2Str);
        
        System.out.println("=============================================================");
        int[] arr3 = {8,9,1,7,2,3,5,4,6,0};
        System.out.println("排序前");
        System.out.println(Arrays.toString(arr3));
        shellSort2(arr3);
        System.out.println("排序后");
        System.out.println(Arrays.toString(arr3));
        
        //测试希尔排序（移位法）的速度
        int[] arr4 = new int[80000];
        for(int i = 0;i < 80000;i++) {
            arr4[i] = (int)(Math.random() * 80000);
        }
        Date date3 = new Date();
        SimpleDateFormat simpleDateFormat1 = new SimpleDateFormat("yyy-MM-dd HH:mm:ss");
        String date3Str1 = simpleDateFormat1.format(date3);
        System.out.println("移位法排序前的时间=" + date3Str1);
        
        shellSort2(arr4);
        
        Date date4 = new Date();
        String date4Str = simpleDateFormat1.format(date4);
        System.out.println("移位法排序后的时间=" + date4Str);
    }
    
    //1.交换法
    public static void shellSort(int[] arr) {
/*        int temp = 0;//辅助交换
        //第一次:10个数据分成5组
        for(int i = 5;i < arr.length;i++) {
            //遍历各组所有元素（共5组，每组2个元素），步长为5
            for(int j = i - 5;j >= 0;j -= 5) {
                //如果当前元素大于加上步长的元素，则交换
                if (arr[j] > arr[j+5]) {
                    temp = arr[j];
                    arr[j] = arr[j+5];
                    arr[j+5] = temp;
                }
            }
        }
        System.out.println("第一次\n" + Arrays.toString(arr));//[3, 5, 1, 6, 0, 8, 9, 4, 7, 2]
        
        //第二次:10个数据分成5/2=2组
        for(int i = 2;i < arr.length;i++) {
            //遍历各组所有元素（共2组，每组5个元素），步长为2
            for(int j = i - 2;j >= 0;j -= 2) {
                //如果当前元素大于加上步长的元素，则交换
                if (arr[j] > arr[j+2]) {
                    temp = arr[j];
                    arr[j] = arr[j+2];
                    arr[j+2] = temp;
                }
            }
        }
        System.out.println("第二次\n" + Arrays.toString(arr));//[0, 2, 1, 4, 3, 5, 7, 6, 9, 8]
        
        //第三次:10个数据分成5/2=2/2=1组
        for(int i = 1;i < arr.length;i++) {
            //遍历各组所有元素（共1组，每组10个元素），步长为1
            for(int j = i - 1;j >= 0;j -= 1) {
                //如果当前元素大于加上步长的元素，则交换
                if (arr[j] > arr[j+1]) {
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
        System.out.println("第三次\n" + Arrays.toString(arr));//[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
*/

        int temp = 0;
        for(int gap = arr.length/2;gap > 0;gap /= 2) {
            for(int i = gap;i < arr.length;i++) {
                //遍历各组所有元素,共gap组，步长为gap
                for(int j = i - gap;j >= 0;j -= gap) {
                    //如果当前元素大于加上步长的元素，则交换
                    if (arr[j] > arr[j+gap]) {
                        temp = arr[j];
                        arr[j] = arr[j+gap];
                        arr[j+gap] = temp;
                    }
                }
            }
        }
    }
    
    
    
    //2.移位法
    public static void shellSort2(int[] arr) {
        for(int gap = arr.length/2;gap > 0;gap /= 2) {
            //从第gap个元素，逐个对其所在组进行直接插入
            for(int i = gap;i < arr.length;i++) {
                int j = i;//保存待插入位置下标
                int temp = arr[j];//保存待插入的数
                if (arr[j] < arr[j - gap]) {
                    while(j - gap >= 0 && temp < arr[j - gap]) {
                        //移动
                        arr[j] = arr[j - gap];
                        j -= gap;
                    }
                    //退出while循环后，说明找到了插入位置
                    arr[j] = temp;
                }
            }
        }
    }
}