关于算法-数据结构:排序算法总结Java实现

31次阅读

共计 10253 个字符,预计需要花费 26 分钟才能阅读完成。

排序算法分类

排序算法依据解决数据应用到的存储设备可分为两大类,别离是外部排序和内部排序。

  • 外部排序:将须要解决的数据都加载到内存中进行排序
  • 内部排序:因为数据量过于宏大,单靠内存无奈实现,须要借助内部存储进行排序

外部排序又可细分,如下图所示

插入排序

1. 间接插入排序

  • 基本思路:首先先从数组中抉择一个数 x 放到一个数组里,从遍历以后数组,和新数组的每一个元素进行比拟,从而决定它放在什么地位,只能以后数组的每个元素都放进去了
  • 举个例子,数组{7,5,9,3,12,8,20,18}, 总共须要 7 趟,假如咱们抉择 7 作为第一个数

初始状态:(7),5,9,3,12,8,20,18,从下标 1 开始找,放到新数组里 (7)
第 1 趟:(5,7),9,3,12,8,20,18
第 2 趟:(5,7,9),3,12,8,20,18
第 3 趟:(3,5,7,9),12,8,20,18
第 4 趟:(3,5,7,9,12),8,20,18
第 5 趟:(3,5,7,8,9,12),20,18
第 6 趟:(3,5,7,8,9,12,20),18
第 7 趟:(3,5,7,8,9,12,18,20)

  • 代码如下:
public static void insertSort(int[] arr){if (arr == null || arr.length <= 0) return;
        int len = arr.length;
        for (int i = 1; i < len; i ++){
            // 保留以后地位的值
            int insertValue = arr[i];
            // 找到以后地位的前一个地位
            int insertIndex = i - 1;
            // 和前一个地位进行比拟,只有比前一个小,就把前一个地位的值赋给以后地位
            // 始终循环上来,直到本人成为了第一个数或者找到了一个比本人还小的数
            while (insertIndex >= 0 && insertValue < arr[insertIndex]){arr[insertIndex + 1] = arr[insertIndex];
                insertIndex--;
            }
            // 把之前保留的数和赋给以后找到的地位
            arr[insertIndex + 1] = insertValue;
        }
    }

2. 希尔排序

  • 基本思路:先将整个待排序的记录宰割成若干子序列,别离对这些子序列进行排序,待整个残缺的序列根本有序时,再对整体记录进行顺次间接插入排序
  • 举个例子:比方对于数组{9,12,8,98,36,29,190,54}

    • 1)初始数组如下:
    • 2)抉择一个增量 gap,通常是数组长度的一半,这里 gap 取 4
    • 对同一子序列进行排序,排序后果如下:
    • 3)对上一轮排序的后果再次抉择一个重量,gap 取上一次 gap 的一半为 2,排序后果如下:
    • 4)再次取上一次 gap 的一半,为 1,此时排序的是整个数组,排序后果如下,
    • 当 gap 为 1 时,整个数组曾经排好序
  • 代码如下:

    • 实现希尔排序有两种算法,一种是交换法一种是移位法,前者的效率没有后者的高
public class ShellSort {public static void change(int[] arr, int aIndex, int bIndex){int temp = arr[aIndex];
 arr[aIndex] = arr[bIndex];
 arr[bIndex] = temp;
 }
    // 交换法
 public static void sort(int[] arr){
        int temp = 0;
 for (int gap = arr.length/2; gap > 0; gap /= 2){for (int i = gap; i < arr.length; i++){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;
 }
                }
            }
        }
    }
    // 移位法
 public static void sort2(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;
 }
                    arr[j] = temp;
 }
            }
        }
    }
    public static void main(String[] args) {int[] arr = {7,5,9,3,12,8,20,18};
        sort2(arr);
        System.out.println(Arrays.toString(arr));
 }
}

抉择排序

1. 简略抉择排序

  • 基本思路:从数组中找到一个最大数, 和数组的最初一个数替换(也能够最小),而后再从第一个开始到倒数第二个找到最大数和倒数第二个数替换,反复这样做,直到只剩一个第一个数,这样整个数组的序就排好了
  • 举个例子,数组{7,5,9,3,2,1,12,20}, 总共须要 7 趟(数组的长度 – 1)

第一趟:最大数为 20,和第 7 个数替换,7,5,9,3,2,1,12,20
第二趟:最大数为 12,和第 6 个数替换,7,5,9,3,2,1,12,20
第三趟:最大数为 9,和第 5 个数替换,7,5,1,3,2,9,12,20
第四趟:最大数为 7,和第 4 个数替换,2,5,1,3,7,9,12,20
第五趟:最大数为 5,和第 3 个数替换,2,3,1,5,7,9,12,20
第六趟:最大数为 3,和第 2 个数替换,2,1,3,5,7,9,12,20
第七趟:最大数为 2,和第 1 个数替换,1,2,3,5,7,9,12,20

  • 代码如下:

    public static int[] selectSort(int[] arr){if (arr == null || arr.length <= 0) return null;
            int len = arr.length;
            for (int i = 0; i < len - 1; i ++){
                int maxIndex = 0;
                for (int j = 0; j < len - i; j ++){if (compare(arr[j], arr[maxIndex])){maxIndex = j;}
                }
                change(arr, maxIndex, len - 1 - i);
            }
            return arr;
        }
    
    private static boolean compare(int a, int b){if (a > b)
                return true;
            return false;
        }
    
        private static void change(int[] arr, int a, int b){int temp = arr[a];
            arr[a] = arr[b];
            arr[b] = temp;
        }

2. 堆排序

  • 后期常识

    • 要理解堆排序,必须晓得堆这种数据结构,堆是一个近似齐全二叉树,这种数据结构有个个性,即子节点的键值或索引总是小于(大于)它的父节点,而堆又分为大项堆和小项堆
    • 1)大项堆:每个节点的值都大于或等于其子节点的值
    • 2)小项堆:每个节点的值都小于或等于其子节点的值
    • 比方:

  • 基本思路

    • 1)把待排序的数组构建成一个大根堆,此时最大值就是根元素
    • 2)把堆首元素和堆尾元素进行调换,此时最大值就在堆尾
    • 3)把堆的第一个元素到堆长度 - 1 个元素进行第一和第二步操作,直到堆的长度为 1
  • 举个例子,数组{1,5,9,10,19,8}

    • 1)首先找到第一个元素,发现它没有父节点,则不替换
    • 2)找到第二个元素 5,发现它比父节点的值 1 还要大,两个元素进行替换
    • 3)找到第三个元素 9,发现它比父节点的值 5 还要大,两个元素进行替换
    • 4)找到第四个元素 10,发现它比父节点的值 1 还要大,两个元素进行替换,替换之后发现它还是比父节点的值 9 大,两个元素再进行替换
    • 5)找到第五个元素 19,发现它比父节点的值 9 大,两个元素进行替换,替换之后发现它还是比父节点的值 10 大,两个元素再进行替换
    • 6)找到第六个元素 8,发现它比父节点的值 5 大,两个元素进行替换
    • 7)上述 6 步骤把整个数组构建成了大项堆,之后把堆首元素 19 和堆尾元素 5 进行替换
    • 8)之后再把数组的 length – 1 个元素构建成大项堆,再次替换,直到要构建的数组的长度只剩一个
  • 代码如下
public class HeapSort{public static void swap(int[] arr, int i, int j){int temp = arr[i];  
        arr[i] = arr[j];  
        arr[j] = temp;  
    }  
    public static void main(String[] arg){int[] arr = {1,5,2,4,9,10};  
         heapSort(arr);  
         System.out.println(Arrays.toString(arr));  
    }  

    public static void heapSort(int[] arr){  
            // 结构大根堆  
         int size = arr.length;  
         System.out.println("1)结构大根堆:");  
         heapInsert(arr,0 , size);  
         int i = 1;  
         while (size > 1){  
                    // 固定最大值  
         swap(arr, 0 , size - 1);  
         System.out.print("t 第" + i + "次固定最大值:");  
         System.out.println(Arrays.toString(arr));  
         size --;  
         // 结构大根堆  
         System.out.println((++ i)+")结构大根堆:");  
         heapify(arr, 0 , size);  
         }  
    }  

        // 结构大根堆(通过新插入的数回升)public static void heapInsert(int[] arr, int start, int length){for (int i = start; i < length; i ++){  
                // 以后插入的索引  
                 int currentIndex = i;  
                 // 父节点索引  
                 int fatherIndex = (currentIndex - 1)/2;  
                 while (arr[currentIndex] > arr[fatherIndex]){  
                                // 替换以后节点与父节点的地位  
                 swap(arr, currentIndex, fatherIndex);  
                 // 从新计算以后节点与父节点的索引  
                 currentIndex = fatherIndex;  
                 fatherIndex = (currentIndex - 1) / 2;  
                 }  
                System.out.println("t 第" + i + "次替换:" + Arrays.toString(arr));  
     }  
        }  

        // 将残余的数结构储层大根堆  
     public static void heapify(int[] arr, int index, int size){  
            int left = 2 * index + 1;  
     int right = 2 * index + 2;  
     while (left < size){  
                int largestIndex = index;  
     // 判断孩子中较大的值的索引(确保右孩子在 size 范畴之内)if (arr[left] < arr[right] && right < size){largestIndex = right;}else {largestIndex = left;}  
                // 比拟父节点的值与孩子中较大的值,并确定最大值的索引  
     if (arr[index] > arr[largestIndex]){largestIndex = index;}  
                // 如果父节点索引是最大值的索引,那曾经是大根堆了,则推出循环  
     if (index == largestIndex){break;}  
                // 父节点不是最大值,与孩子中较大的值替换  
     swap(arr, largestIndex, index);  
     System.out.println("tleft:" + left + "tright:" + right);  
     System.out.println("tindex:" + index);  
     System.out.println("tlargestIndex:" + largestIndex);  
     System.out.println("t 替换:" + Arrays.toString(arr));  
     // 将索引指向孩子中较大的值的索引  
     index = largestIndex;  
     // 从新计算替换之后的孩子的索引  
     left = 2 * index + 1;  
     right = 2 * index + 2;  
     }  
        } 
  
}

替换排序

1. 冒泡排序

  • 基本思路:排序从前向后,顺次比拟相邻元素的值,如果前一个元素比后一个元素小,则两个元素调换地位。
  • 举个例子:如下数据 {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48}
    用最根底的办法进行比拟:

第一趟:3,38,5,44,15,36,26,27,2,46,4,19,47,48,50
第二趟:3,5,38,15,36,26,27,2,44,4,19,46,47,48,50
第三趟:3,5,15,36,26,27,2,38,4,19,44,46,47,48,50
第四趟:3,5,15,26,27,2,36,4,19,38,44,46,47,48,50
第五趟:3,5,15,26,2,27,4,19,36,38,44,46,47,48,50
第六趟:3,5,15,2,26,4,19,27,36,38,44,46,47,48,50
第七趟:3,5,2,15,4,19,26,27,36,38,44,46,47,48,50
第八趟:3,2,5,4,15,19,26,27,36,38,44,46,47,48,50
第九趟:2,3,4,5,15,19,26,27,36,38,44,46,47,48,50
第十趟:2,3,4,5,15,19,26,27,36,38,44,46,47,48,50
第十一趟:2,3,4,5,15,19,26,27,36,38,44,46,47,48,50
第十二趟:2,3,4,5,15,19,26,27,36,38,44,46,47,48,50
第十三趟:2,3,4,5,15,19,26,27,36,38,44,46,47,48,50
第十四趟:2,3,4,5,15,19,26,27,36,38,44,46,47,48,50
第十五趟:2,3,4,5,15,19,26,27,36,38,44,46,47,48,50

  • 代码实现:
    一般来说,有几个数咱们就要循环几趟,然而有的时候其实可能整个数组的程序曾经排序好了,然而可能还剩好几趟,比方下面的例子中,在第十趟的时候其实曾经排号序了。所以在代码实现中,设置一个标记,如果一趟下来都没有两个相邻数之间进行替换,则示意整个数组曾经排好序了,所以间接跳出循环。
public class Bubble {

    // 比拟两个数的大小
    public static boolean compare(int a, int b){if (a > b){return true;}
        return false;
    }

    // 替换两个数的地位
    public static void change(int[] arr, int aIndex, int bIndex){int temp = arr[aIndex];
        arr[aIndex] = arr[bIndex];
        arr[bIndex] = temp;
    }

    public static void sort(int[] arr){
        boolean flag = false;// 标记位
        for (int i = 0; i < arr.length - 1; i++){for (int j = 0; j < arr.length - i -1;j++){if (compare(arr[j], arr[j + 1])){
                    flag = true;
                    change(arr, j, j+1);
                }
            }
            if (!flag){break;}else {flag = false;}
        }
    }
}

2. 疾速排序

  • 基本思路:首先找到一个基准数,比这个数大的放到它的右边,比这个数小的放到它的左边,而后再别离对它的左右两边进行雷同的操作,直到左右两边的数都排好序。
  • 举个例子:数组 arr={12,18,6,9,14,8,4,3,19},咱们把数组的每一位数设想成一个房间,每个房间里装着一个人
  • 令 i = 0,j = 8,x=arr[i]; i 代表最右边的下标,j 代表最左边的下标,x 为基准数
  • 首先咱们须要对 arr 进行第一次排序,让 x 右边全都是比它小的数,x 的左边全都是比它大的数,咱们从下标 j 开始往前查找,咱们先把 x 从房间里请进去,此时 arr[0]的房间是空的(但实际上这个房间还是有人的,这样是为了不便了解)
  • 从后往前找,直到找到比 x 小的数 :咱们发现 arr[8] 并不大于 x,那么令 j –, 这时咱们发现 arr[7]= 3 是小于 x 的,那么此时咱们把 3 赋给 arr[0],这就相当于把房间 7 的人放到了房间 0 外面,这时房间 7 空了,前面的房间空了就须要后面的房间来补

    • 此时数组为 arr={3,18,6,9,14,8,4,3,19},i=0,j=7
  • 从前往后找,直到找到比 x 大的数 :此时 arr[0] 并不大于 x,令 i ++,发现 arr[1]=18 大于 12,那咱们就能够把房间 1 的人放到空房间 7

    • 此时数组为 arr={3,18,6,9,14,8,4,18,19},i=1,j=7
  • 当初是房间 1 空了,从后往前找,发现 arr[6]= 4 小于 x,把房间 6 的人放到了房间 1

    • 此时数组为 arr={3,4,6,9,14,8,4,18,19},i=1,j=6
  • 当初是房间 6 空了,从前往后找,发现 arr[4]=14 大于 x,把房间 4 的人放到了房间 6

    • 此时数组为 arr={3,4,6,9,14,8,14,18,19},i=4,j=6
  • 当初是房间 4 空了,从后往前找,发现 arr[5]小于 x,把房间 5 的人放到了房间 6

    • 此时数组为 arr={3,4,6,9,8,8,14,18,19},i=4,j=5
  • 当初是房间 5 空了,从前往后找,发现 arr[5]不大于 x,并且 i 和 j 相等了,那么第一次排序就完结了,站在门外的 x 进去了房间 5

    • 此时数组为 arr={3,4,6,9,8,12,14,18,19}
  • 当初就把 12 右边的数再进行一次排序,12 左边的数再进行一次排序,反复进行直到整个数组排序排好了

代码如下:

public static void quickSort(int[] arr, int start, int end){
        // 边界条件
        if (arr == null || arr.length <= 1 || start >= end) return;
        // 设置基准值 x,右边索引 i,左边索引 j
        int i = start,j = end;
        int x = arr[i];
        // 只有 i 大于等于 j, 就始终找
        while (i < j){while (i < j && arr[j] >= x) j --;
            if (i < j)
                arr[i] = arr[j];
            while (i < j && arr[i] < x) i ++;
            if (i < j)
                arr[j] = arr[i];
        }
        arr[i] = x;
        // 左右两边递归排序
        quickSort(arr, start, i - 1);
        quickSort(arr, i + 1, end);
    }

归并排序

  • 基本思路:

    • 归并排序是采纳分而治之的思维,将待排序的数组分成若干个数组,对每个数组进行排序,而后再将排序好的数组合并,如下图所示
  • 举个例子:数组{1,4,6,7,9,2,3,5}

    • 联合上图,首先对整个数组进行递归等分,直到被合成进去的数组的长度为 1,而后对相邻的两个数组进行 有序 的合并,直到所有扩散的数组合并成一个有序数组
    • 合并的步骤:比方上图中的数组 {1,4,6,7} 和数组 {2,3,5,9} 的合并,首先左边数组的第一个元素和右边数组的第一个元素进行比拟,如果左边的小则把该元素放到一个长期的数组 temp 里存着,反过来也是一样。直到左右两边有一边被解决完,而后把残余的另一边的数组填充到 temp 数组里,这样就合并实现
  • 代码如下:
    public class Test {public static void main(String[] args) {int arr[] = {8, 4, 5, 7, 1, 3, 6, 2};  
     mergeSort(arr, 0, arr.length - 1, new int[arr.length]);  
     System.out.println(Arrays.toString(arr));  
     }  
        // 分 + 并  
     public static void mergeSort(int[] arr, int left, int right, int[] temp){if (left < right){int mid = (left + right) / 2;  
     // 向左递归合成  
     mergeSort(arr, left, mid, temp);  
     // 向右递归合成  
     mergeSort(arr, mid + 1, right, temp);  
     // 合并  
     merge(arr, left, mid, right, temp);  
     }  
        }  

        // 合并的办法  

     /**  
     * @param arr 待排序的数组  
     * @param left 右边有序序列的起始索引  
     * @param mid 两头索引  
     * @param right 左边有序序列的开端索引  
     * @param temp 长期存储的数组  
     */  
     public static void merge(int[] arr, int left, int mid, int right, int[] temp){  
            int i = left; // i 指向右边有序序列的起始索引  
     int j = mid + 1; // j 指向左边有序序列的起始索引  
     int t = 0; // t 指向 temp 数组的以后索引  

     //1)首先,把左右两边的数据填充到 temp 数组中  
     // 直到左右两边的有序序列有一边曾经处理完毕  
     while (i <= mid && j <= right){  
                // 如果右边的有序序列的以后元素小于等于左边的,则填充到 temp 数组,反之亦然  
     // 填充完之后索引值递增  
     if (arr[i] <= arr[j]){temp[t] = arr[i ++];  
     }else {temp[t] = arr[j ++];  
     }  
                t ++;  
     }  
            //2)把残余一边的有序序列填充到 temp 数组中  
     while (i <= mid){// 如果右边序列还有残余,则解决  
     temp[t ++] = arr[i ++];  
     }  
            while (j <= right){// 如果左边序列还有残余,则解决  
     temp[t ++] = arr[j ++];  
     }  

            //3)把 temp 数组的元素拷贝到 arr 数组  
     // 并不是每次 temp 数组的总元素都和 arr 数组相等  
     t = 0; // 初始化 temp 的起始索引  
     int tempLeft = left; // 获取右边序列的起始索引  
     while (tempLeft <= right){arr[tempLeft ++] = temp[t ++];  
     }  
        }  
    }

基数排序

  • 举例说明:比方待排序数组为{53, 42, 9, 4, 128, 64, 989}

    • 1)首先,获取所有元素的个位数,依据个位数放入到对应的桶中(桶有 10 个),而后按序将放入桶中元素拿出赋给原来的数组,则第一趟的后果为:42,53,4,64,128,9,989
    • 2)而后获取所有元素的十位数,依据十位数放入到对应的桶中,如果位数不够的主动补 0,放入到 0 号桶中,则第二趟的后果为:4,9,128,42,53,64,989
    • 3)最初获取所有元素的百位数,依据百位数放入到对应的桶中,如果位数不够的话也是主动补 0,则第三趟的后果为:4,9,42,53,64,128,989
    • 留神:趟数和该元素的最大值的位数统一,如果该数组有千位的话还须要进行第四趟,依据千位数进行排序
  • 代码如下:
    public class RadixSort {public static void main(String[] args) {int arr[] = {53, 3, 542, 748, 14, 214};  
     radixSort(arr);  
     }  

        public static void radixSort(int[] arr){  
            //1、获取 arr 数组中的最大值的位数  
     int max = arr[0];  
     for (int temp : arr){if (temp > max){max = temp;}  
            }  
            int maxLength = (max + "").length();  
     //2、初始化桶、以及每个桶对应的索引  
     // 每个桶的长度为 arr 的长度(取最坏的状况)int[][] bucket = new int[10][arr.length];  
     // 记录每个桶理论放了多少数据  
     int[] bucketEleCounts = new int[10];  

     //3、循环解决桶  
     for (int i = 0, n = 1; i < maxLength; i ++, n *= 10){  
                // 遍历数组,对每个数组的对应位进行排序解决(从个位数开始)for (int j = 0; j < arr.length; j ++){  
                    // 获取该元素的对应位的值  
     int digit = arr[j] / n % 10;  
     // 通过 digit,将该元素放入绝对应的桶中  
     bucket[digit][bucketEleCounts[digit] ++] = arr[j];  
     }  
                // 依照桶的顺组,将每个桶中的数据放入到原来的 arr 数组中  
     int index = 0; // 记录 arr 数组以后地位  
     // 遍历每一个桶  
     for (int k = 0; k < bucketEleCounts.length; k ++){  
                    // 如果桶中有数据咱们才放入 arr 中  
     int count = bucketEleCounts[k];  
     if (count != 0){  
                        // 循环第 k 个桶,将数据放入 arr 中  
     for (int l = 0; l < count; l ++){arr[index ++] = bucket[k][l];  
     }  
                        // 每一轮解决过后,须要将 bucketEleCount 清零,为下一轮做筹备  
     bucketEleCounts[k] = 0;  
     }  
                }  
                System.out.println("第" + (i + 1) + "轮,arr =" + Arrays.toString(arr));  
     }  

        }  
    }

正文完
 0