本文共 6104 字，大约阅读时间需要 20 分钟。

直接插入排序

插入排序的基本思想是往有序的序列当中插入一个元素,整个的区间被分为有序区间和无序区间,刚开始默认数组的第一个元素为有序区间,此时无序区间就是[1 , arr.length-1]范围,每次将无序区间里的第一个元素和有序区间进行比较,使得无序区间里的第一个元素插入之后,数组仍然是有序;

public static void insertSort(int[] arr){
           //bound表示无序数组是从数组的第二个元素开始,里层循环就是和有序数组进行比较交换操作;        for(int bound = 1; bound < arr.length; bound ++){
               for(int cur = bound -1;cur >= 0; cur --){
                   if(arr[cur] > arr[cur + 1]){
                       int temp = arr[cur + 1];                    arr[cur + 1] = arr[cur];                    arr[cur] = temp;                }            }        }    }

希尔排序

希尔排序是直接插入排序的一种,是将无序数列分为若干个子序列,对这些子序列分别进行插入排序;

public static void shellSort(int[] arr){
           int gap = arr.length / 2;        while (gap >= 1){
               for (int bound = gap;bound < arr.length; bound ++){
                   for(int cur = bound - gap;cur >= 0; cur -= gap){
                       if(arr[cur] > arr[cur + gap] ){
                           int temp = arr[cur + gap];                        arr[cur + gap] = arr[cur];                        arr[cur] = temp;                    }                }            }            gap = gap /2;        }    }

直接选择排序;

排序原理,每一次从无需区间里面选择一个最大(最小)的元素,放在无序区间的最后面(最前面),直到代拍元素的数据排完为止;

//选择排序    public static void selectSort(int[] arr){
           for (int i = 0; i < arr.length; i++) {
               for (int j = i + 1; j < arr.length; j++){
                    if(arr[j] < arr[i]){
                        int temp = arr[j];                     arr[j] = arr[i];                     arr[i] = temp;                 }            }        }    }    public static void selectSort2(int[] arr){
           //挑选一个最大的元素放在数组的最后面;        //需要注意需要第一层循环是从后往左走,因为最大元素需要放在最右边;        for(int i = arr.length - 1; i >= 0;i--){
               for(int j = i - 1 ; j >= 0; j--){
                   if(arr[i] < arr[j]){
                       int temp = arr[i];                    arr[i] = arr[j];                    arr[j] = temp;                }            }        }    }

堆排序

堆排序的基本原理和元组排序的原理相同,选择数组当中最大的元素或者最小的元素及逆行依次排列,在堆排序中的体现就是根据大堆或者小堆的方式体现第一步:将一个无序的序列构建成一个大堆或者小堆,;接下来将堆顶元素和堆末尾的元素进行交换,末尾的元素,也就是删除之前的堆顶元素,再将堆进行向上调整或者向下调整,依次循环

//堆排序    public static void heapSort(int[] arr){
           //建立堆        creatHeap(arr);        //循环取出堆顶元素,将对顶元素和最后一个元素进行交换,交换之后,size--,最后一个元素删除,将堆顶元素先后下调整        int size = arr.length;        for (int i = 0;i < arr.length; i++){
               int temp = arr[0];            arr[0] = arr[size -1];            arr[size - 1] = temp;            size -- ;            shiftDown(arr,0);        }    }    //构造堆    public static void creatHeap(int[] arr){
           for (int i = (arr.length -1 -1) /2; i >= 0 ; i--) {
               shiftDown(arr,i);        }    }    //堆的向下调整    public static void shiftDown(int[] arr,int index){
           int parent = index;        int size = arr.length;        int child = parent * 2 + 1;        while (child < size){
               //先找出最大值            if(arr[child] < arr[child + 1] && child + 1 < size){
                   child ++;            }            //找出最大值子节点,父子节点进行交换            if(arr[parent] < arr[child]){
                   int temp = arr[parent];                arr[parent] = arr[child];                arr[child] = temp;            }            //交换完成之后,继续向下进行调整            parent = child;            child = 2*parent + 1;        }    }

冒泡排序

基本原理,在无序区间通过相邻元素的比较,将最大的数或者最小的数冒泡到无序区间的末尾或者前端,直到整个数组成为有序

//冒泡排序    public static void bubbleSort(int[] arr){
           for (int i = 0; i < arr.length; i++){
               for (int j = 0; j < arr.length - i - 1; j++){
                   if(arr[j] > arr[j + 1]){
                       int temp = arr[j];                    arr[j] = arr[j + 1];                    arr[j + 1] = temp;                }            }        }    }

快速排序;

核心操作:现在待排序区间寻找一个基准值,然后把这个数组整理成左边比基准值大的数右边比基准值小的数,

//快速排序    /**     *     * @param arr 排序数组     * @param left 开始时左边的索引值     * @param right 开始时右边的索引值,也就是arr.length -1;     */    public static void quickSort(int[] arr,int left,int right){
           if(left > right){
               return;        }        //递归条件进行判断:相当于每一次递归的遍历,左边哨兵的值,永远要比右边的值小        int i = left;        int j = right;        int position = arr[left];        //第一次首先把基准位置position设为left也就是数组的第一个元素        //每一次的递归left和right位置都会发生改变        while(i < j){
               //循环里面需要将所有小于基准数的值放在基准数的左边,大于基准值的数放在基准值的右边            //想从右边开始,找比基准值小的数,这里的条件必须是小于等于,不能时小于,满足排序的稳定性,            while(position <= arr[j] && i < j){
                   j --;            }            while (position >= arr[i] && i < j){
                   i ++;            }            //走到这里需要进行判断,看left的值是否比right的大如果是,进行交换,不是,说明两者相遇,将靳准之进行替换,            // 本地循环结束,继续进行递归            if(i < j){
                   int temp = arr[i];                arr[i] = arr[j];                arr[j] = temp;            }        }        //此时跳出while循环,将基准值进行交换        arr[left] = arr[i];        arr[i] = position;        quickSort(arr,left,i - 1);        quickSort(arr,j + 1,right);    }

归并排序

归并排序的思想是不断的将数组进行拆分,直到拆分为子项为1,再将数组合并的过程

private static void merge(int[] arr, int left, int mid, int right) {
           if(left >= right){
               return;        }        int temp[] = new int[right - left];        //临时数组的空间下标        int tempIndex = 0;        int cur1 = left;        int cur2 = mid;        while (cur1 < mid && cur2 < right){
               if(arr[cur1] < arr[cur2]){
                   temp[tempIndex] = arr[cur1];                cur1 ++;                tempIndex++;            }else {
                   temp[tempIndex] = arr[cur2];                cur2++;                tempIndex++;            }        }        //将剩剩下没有比较完成的元素放入temp数组        while(cur1 < mid){
               temp[tempIndex] = arr[cur1];            cur1 ++;            tempIndex++;        }        while (cur2 < right){
               temp[tempIndex ] = arr[cur2];            cur2++;            tempIndex++;        }        //将temp的内容拷贝到源数组        int t = 0;        int tempLeft = left;        while (tempLeft < right){
               arr[tempLeft] = temp[t];            tempLeft++;            t++;        }    }

转载地址：http://qqsxi.baihongyu.com/