1. 首页
  2. 文章资讯

Java实现八种排序

9 阅读 0 评论

目录

分类

直接插入排序

希尔排序

选择排序

堆排序

冒泡排序

快速排序

挖坑法

 hoare法 

双指针法

优化

非递归实现 

归并排序

非递归实现

计数排序

分类

这里的排序可以分为两大类，

  • 基于比较的排序
  • 非基于比较的排序

其中有七种基于比较的排序：

  • 直接插入排序
  • 希尔排序
  • 选择排序
  • 堆排序
  • 冒泡排序
  • 快速排序
  • 归并排序

一种非基于比较的排序：计数排序。

下面会通过Java来实现这八种排序，快速排序 和 归并排序 会有递归和非递归的实现。

直接插入排序

思路：

  1. 以两个for循环， 来实现两个数及两数中小数与前面数进行比较
  2. 假设第一个数为tmp，认为第一个数已经是排好序的，然后去和后面一个数进行比较
  3. 如果 j位置 的数 > j+1位置的数，把 j位置的数 赋值给 j+1位置；如果否，则向 j位置的前面去做，直到 j >= 0
  4. 重复进行步骤3，直到不符合循环条件

动图如下：

代码 ：

public static void insertSort(int[] array){
    for (int i = 1; i < array.length; i++) {
        int tmp = array[i];
        int j = i-1;
        for (; j >= 0; j--) {
            if(array[j] > tmp){
                array[j+1] = array[j];
            }else{
                array[j+1] = tmp;
                break;
            }
        }
        array[j+1] = tmp;
    }
}

时间复杂度：O(N^2)

空间复杂度：O(1) 

稳定性：稳定

注意：

  • 本身是一个稳定的排序，那么可以实现为不稳定的 。但是 如果一个排序 本身就是不稳定，那就不能实现稳定的排序。
  • 数据越有序，直接插入排序越快

希尔排序

步骤：

希尔排序算是对直接排序进行优化，把其中的数据通过分组来不断简化 其中的有序性，上面有提到数据越有序，直接插入排序越快，不过这个分组并不是常规理解的那种把几个临近的数字化为一个组，而是，如下图所示：

通过间隔（gap）来实现分组，以上面 紫色的原图 为例，这时的gap为5，这代表着隔着5个空格的数为一组，然后进行组内排序，不断缩小间隔，增加每组内元素个数，再次进一步比较。

动图如下：

代码：

通过代码部分，我们也能看出这里面有直接排序的存在，只不过其中的部分和希尔排序有些出入。

public static void shellInsert(int[] array){
    int gap = array.length;
    while(gap > 1){
        gap /= 2;
        shell(array, gap);
    }
}

private static void shell(int[] array, int gap) {
    for (int i = gap; i < array.length; i++) {
        int tmp = array[i];
        int j = i-gap;
        for (; j >= 0; j-= gap) {
            if(array[j] > tmp){
                array[j+gap] = array[j];
            }else{
                array[j+gap] = tmp;
                break;
            }
        }
        array[j+gap] = tmp;
    }
}

 时间复杂度：O(N^1.2) - O(N^1.3)

空间复杂度：O(1)

稳定性：不稳定

选择排序

第一种思路

步骤：

  1. 选择排序，从名字上我们可以理解为从中不断选择出最小值，然后把它交换、排到前面
  2. 之所以说是不断选出最小值，是因为每次选出最小值都是以 i位置为准，而i位置也会不断变化，两个for循环来实现

动图如下： 

代码：

public static void selectSort(int[] array){
    for (int i = 0; i < array.length; i++) {
        int minIndex = i;
        for (int j = i+1; j < array.length; j++) {
            if(array[j] < array[minIndex]){
                minIndex = j;
            }
        }
        swap(array,i,minIndex);
    }
}

private static void swap(int[] array, int i, int minIndex) {
    int tmp = array[i];
    array[i] = array[minIndex];
    array[minIndex] = tmp;
}

因为其中有元素位置的交换，所以我们可以自己写一个元素位置交换的方法。 

时间复杂度：O(N^2)   和数据 是否有序无关

空间复杂度：O(1)

稳定性：不稳定

第二种思路

步骤：

这里主要是通过双指针的方法来找到 最小值 和 最大值的位置，当然，这是相对于每次i位置的数的大小。整体过程和上面一种思路有些相似的部分，相对来说，掌握两种方法还是要好一点。

public static void selectSort1(int[] array){
    int left = 0;
    int right = array.length-1;
    while(left < right){
        int minIndex = left;
        int maxIndex = left;
        for (int i = left+1; i <= right; i++) {
            if(array[i] < array[minIndex]){
                minIndex = i;
            }
            if(array[i] > array[maxIndex]){
                maxIndex = i;
            }
        }
        swap(array, left, minIndex);
        //确保最大值的位置，最大值正好是 left 下标
        //此时把最大值换到了minIndex下标
        if(maxIndex == 0){
            maxIndex = minIndex;
        }
        swap(array, right, maxIndex);
        left++;
        right--;
    }
}

private static void swap(int[] array, int i, int minIndex) {
    int tmp = array[i];
    array[i] = array[minIndex];
    array[minIndex] = tmp;
}

堆排序

步骤：

  1. 通过向下调整，创建一棵大根堆的树
  2. 通过把根节点和最后一个分支节点进行交换
  3. 再进行向下调整，完成排序

这个思路主要是通过大根堆的由大到小的原理，再通过换位来实现排序。

代码：

public static void heapSort(int[] array){
    createHeap(array);

    int end  = array.length-1;
    while(end > 0){
        swap(array, 0 ,end);
        siftDown(array, 0,end);
        end--;
    }
}

//创建大根堆
public static void createHeap(int[] array){
    //length-1为最后一棵子树，-1 / 2 是为了找到最后一棵子树的根节点
    for (int parent = (array.length-1-1)/2; parent >= 0; parent--) {
        siftDown(array,parent,array.length);//向下调整，创建大根堆
    }
}

/**
 *
 * @param array
 * @param parent 每棵子树调整的根节点
 * @param length 每棵子树调整的结束节点，跳到最后
 */
public static void siftDown(int[] array, int parent, int length) {
    int child = 2*parent+1;
    while(child < length){
        if(child + 1 < length && array[child] < array[child +1]){
            child++;
        }

        if(array[child] > array[parent]){
            swap(array, child, parent);
            parent = child;
            child = 2*parent+1;
        }else{
            break;
        }
    }
}

private static void swap(int[] array, int i, int minIndex) {
    int tmp = array[i];
    array[i] = array[minIndex];
    array[minIndex] = tmp;
}

时间复杂度：O(N*logN)
空间复杂度：O(1)

稳定性：不稳定

冒泡排序

步骤：

通过相邻的两个元素相互比较，若 前位置 比 后位置的数要大，进行交换

动图如下：

下面代码部分是优化后的部分，未优化则不包含(flg元素 和 -i操作 )

代码：

public static void bubbleSort(int[] array){
    for (int i = 0; i < array.length-1; i++) {
        boolean flg = false;
        for (int j = 0; j < array.length-1-i; j++) {
            if(array[j] > array[j+1]){
                swap(array, j, j+1);
                flg = true;
            }
        }
        //优化后的情况
        //n个数据，比较n-1次，有可能其中i次就有序了
        if(!flg){
            break;
        }
    }
}

private static void swap(int[] array, int i, int minIndex) {
    int tmp = array[i];
    array[i] = array[minIndex];
    array[minIndex] = tmp;
}

时间复杂度：不优化的情况（没有下方的boolean元素和-i操作） O(n^2)

                     优化以后，最快情况能达到O(N)

空间复杂度：O(1) 

稳定性：稳定

快速排序

快速排序有三种方式能来实现

  • 挖坑法
  • hoare法
  • 双指针法

如果问题问到快速排序，优先使用挖坑法，其次hoare法、双指针法

挖坑法

步骤：

  1. 先是实现 保证一个数的左边都比它小，右边都比它大，具体步骤如下步骤2，3，4
  2. 把第一个数存起来，为tmp，第一个位置当作是坑
  3. 从后面找比tmp小的值，放到坑里面，后面被放入坑的数的位置再当作坑
  4. 从前面找比tmp大的值，放到坑里面，前面被放入坑的数的位置当作坑
  5. 再向两边进行递归来处理

动图如下：

代码：

public static void quickSort(int[] array){
    quick(array,0,array.length-1);
}

private static void quick(int[] array, int start, int end){
    // = 是为了应对没有右边的情况，递归结束条件
    if(start >= end){
        return;
    }
    //整个方法走完之后，为第一次交换位置
    int pivot = partition1(array, start, end);
    quick(array, start, pivot-1);
    quick(array, pivot+1, end);
}

private static int partition1(int[] array, int left, int right) {
    int tmp = array[left];
   
    while(left < right){
        //循环找，不循环时则代表找到，找到比tmp小的数
        while(left < right && array[right] >= tmp){
            right--;
        }
        //挖坑法，然后填坑
        //先是把第一个位置当作空，从后面数，如果有数比它小，就放到第一位
        //然后是从前数，找最大值，找到后放到，刚刚的位置
        //最后再把第一个数放到right和left相交的位置
        //方法就是把两边的数分大小放到第一个数两边
        array[left] = array[right];


        //找到比tmp大的数
        while(left < right && array[left] <= tmp){
            left++;
        }
        array[right] = array[left];
    }
    array[left] = tmp;
    return left;
}

 hoare法 

步骤：

  1. 先是实现 保证一个数的左边都比它小，右边都比它大，具体步骤如下步骤2，3，4
  2. 把第一个数存起来，为tmp
  3. tmp和后面的数进行比较，然后把小数放到tmp前面，大数放到tmp后面
  4. 递归实现对tmp两边进行排序

代码如下：

public static void quickSort(int[] array){
    quick(array,0,array.length-1);
}

private static void quick(int[] array, int start, int end){
    // = 是为了应对没有右边的情况，递归结束条件
    if(start >= end){
        return;
    }
    //整个方法走完之后，为第一次交换位置
    int pivot = partition(array, start, end);
    quick(array, start, pivot-1);
    quick(array, pivot+1, end);
}

private static int partition(int[] array, int left, int right) {
    int tmp = array[left];
    int tmpleft = left;

    while(left < right){
        //循环找，不循环时则代表找到
        //right是为了把右边的小数移到左边
        while(left < right && array[right] >= tmp){
            right--;
        }

        while(left < right && array[left] <= tmp){
            left++;
        }
        swap(array, left, right);
    }
    //因为left所找的是把左边的大数放到右边，所以找到最后的数会比left小，进行交换
    swap(array,left,tmpleft);
    return left;
}

private static void swap(int[] array, int i, int minIndex) {
    int tmp = array[i];
    array[i] = array[minIndex];
    array[minIndex] = tmp;
}

双指针法

步骤：

这个主要是靠 cur + left 双指针来实现排序的，通过前后条件判断来进行排序

代码如下：

public static void quickSort(int[] array){
    quick(array,0,array.length-1);
}

private static void quick(int[] array, int start, int end){
    // = 是为了应对没有右边的情况，递归结束条件
    if(start >= end){
        return;
    }
    //整个方法走完之后，为第一次交换位置
    int pivot = partition3(array, start, end);
    quick(array, start, pivot-1);
    quick(array, pivot+1, end);
}

public static int partition3(int[] array, int left, int right){
    int prev = left;
    int cur = left+1;
    while(cur <= right){
        if(array[left] > array[cur] && array[cur] != array[prev]){
            swap(array, cur, prev);
        }
        cur++;
    }
    swap(array,prev,left);
    return prev;
}

private static void swap(int[] array, int i, int minIndex) {
    int tmp = array[i];
    array[i] = array[minIndex];
    array[minIndex] = tmp;
}

关于快速排序

时间复杂度：当数据给定的是1 2 3 4 5 6……有序的情况是 O(n^2) 

                      最好的情况是O(N*logN)均匀分为叉，满二叉树

空间复杂度：最坏情况，递归是要开辟内存的O(N),最好的情况，满二叉树O(logN)

稳定性：不稳定

优化

通过上面三种方法，我们能看到三种方法中都有递归方式，每次递归都需要开辟内存，那么我们可以采取怎样的方式来减少递归的次数？

通过下面两种方法可以实现我们的想法：

  1. 三数取中

  2. 直接插入法【针对一定范围】

关于三数取中的意思是：找到左、右、中三个数的中位数。

 部分直接插入，也可以减少递归次数，因为数据有越有序，直接插入法越快。

代码部分如下：

public class Sort {
    public static void quickSort(int[] array){
        quick(array,0,array.length-1);
    }

    private static void quick(int[] array, int start, int end){
        // = 是为了应对没有右边的情况，递归结束条件
        if(start >= end){
            return;
        }

        if(end - start + 1 <= 7){
            insertSortRange(array, start, end);
            return;
        }
        int minIndex = getMiddleNum(array, start, end);
        swap(array, start, minIndex);

        //整个方法走完之后，为第一次交换位置
        int pivot = partition1(array, start, end);
        quick(array, start, pivot-1);
        quick(array, pivot+1, end);
    }

    public static void insertSortRange(int[] array, int start, int end){
        for (int i = start+1; i <= end; i++) {
            int tmp = array[i];
            int j = i-1;
            for (; j >= start; j--) {
                if(array[j] > tmp){
                    array[j+1] = array[j];
                }else{
                    array[j+1] = tmp;
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }

    private static int getMiddleNum(int[] array, int left, int right){
        int mid = (left+right)/2;
        if(array[left] < array[right]){
            if(array[mid] < array[left]){
                return left;
            }else if(array[mid] > array[right]){
                return right;
            }else{
                return mid;
            }
        }else{
            if(array[mid] > array[left]){
                return left;
            }else if(array[mid] < array[right]){
                return right;
            }else{
                return mid;
            }
        }
    }

    private static int partition1(int[] array, int left, int right) {
        int tmp = array[left];

        while(left < right){
            //循环找，不循环时则代表找到，找到比tmp小的数
            while(left < right && array[right] >= tmp){
                right--;
            }
            //挖坑法，然后填坑
            //先是把第一个位置当作空，从后面数，如果有数比它小，就放到第一位
            //然后是从前数，找最大值，找到后放到，刚刚的位置
            //最后再把第一个数放到right和left相交的位置
            //方法就是把两边的数分大小放到第一个数两边
            array[left] = array[right];


            //找到比tmp大的数
            while(left < right && array[left] <= tmp){
                left++;
            }
            array[right] = array[left];
        }
        array[left] = tmp;
        return left;
    }

    private static void swap(int[] array, int left, int right){
        int tmp = array[left];
        array[left] = array[right];
        array[right] = tmp;
    }
}

非递归实现 

非递归实现，主要是栈的使用，通过控制出栈和入栈的元素及其顺序来实现

代码如下：

public static void quickSort(int[] array){
    quickNor(array,0,array.length-1);
}

private static void quickNor(int[] array, int start, int end){

    Deque<Integer> stack = new ArrayDeque<>();
    int pivot = partition1(array, start, end);
    //pivot左边有两个元素
    if(pivot > start+1){
        stack.push(start);
        stack.push(pivot-1);
    }

    if(pivot < end-1){
        stack.push(pivot+1);
        stack.push(end);
    }

    while(!stack.isEmpty()){
        end = stack.pop();
        start = stack.pop();
        pivot = partition1(array, start, end);
        if(pivot > start+1){
            stack.push(start);
            stack.push(pivot-1);
        }

        if(pivot < end-1){
            stack.push(pivot+1);
            stack.push(end);
        }
    }
}

private static int partition1(int[] array, int left, int right) {
    int tmp = array[left];

    while(left < right){
        //循环找，不循环时则代表找到，找到比tmp小的数
        while(left < right && array[right] >= tmp){
            right--;
        }
        //挖坑法，然后填坑
        //先是把第一个位置当作空，从后面数，如果有数比它小，就放到第一位
        //然后是从前数，找最大值，找到后放到，刚刚的位置
        //最后再把第一个数放到right和left相交的位置
        //方法就是把两边的数分大小放到第一个数两边
        array[left] = array[right];


        //找到比tmp大的数
        while(left < right && array[left] <= tmp){
            left++;
        }
        array[right] = array[left];
    }
    array[left] = tmp;
    return left;
}

private static void swap(int[] array, int left, int right){
    int tmp = array[left];
    array[left] = array[right];
    array[right] = tmp;
}

归并排序

步骤：

  1. 先把要排序的元素分为两个组，接着继续向下分组(有种递归的味道了)
  2. 把每组元素比较完后，再把两个有序数组组合起来

代码如下： 

public static void mergeSort(int[] array){
    mergeSortTmp(array, 0, array.length-1);
}

//递归实现归并排序
private static void mergeSortTmp(int[] array, int left, int right) {
    if(left >= right){
        return;
    }
    //找中间值
    int mid = (left + right)/2;
    mergeSortTmp(array, left, mid-1);
    mergeSortTmp(array, mid+1, right);
    //走到这里，相当于全部分解完
    //合并，合并有序数组
    merge(array, left, mid, right);


}

private static void merge(int[] array, int left, int mid, int right) {
    int[] tmp = new int[right-left+1];
    int k = 0;
    int s1 = left;
    int e1 = mid;
    int s2 = mid+1;
    int e2 = right;

    while(s1 <= e1 &&  s2 <= e2){
        if(array[s1] <= array[s2]){
            tmp[k++] = array[s1++];
        }else {
            tmp[k++] = array[s2++];
        }
    }

    while(s1 <= e1){
        tmp[k++] = array[s1++];
    }

    while(s2 <= e2){
        tmp[k++] = array[s2++];
    }
    //可以保证tmp数组是有序的
    for (int i = 0; i < k; i++) {
        array[i+left] = tmp[i];
    }
}

时间复杂度：O(N*logN)

空间复杂度：O(N)

稳定性：稳定

非递归实现

非递归的实现，主要依靠的间隔gap的不断变大，然后通过每一小部分的排序进而来实现整个数据组的排序

代码如下：

 

public static void mergeSortNor(int[] array){
    int gap =1;
    while(gap < array.length){
        for (int i = 0; i < array.length; i = i + gap*2) {
            int left = i;
            int mid = (left + gap -1);
            if(mid >= array.length){
                mid = array.length-1;
            }
            int right = mid + gap;
            if(right >= array.length){
                right = array.length-1;
            }
            merge(array, left, mid, right);
        }
        gap *= 2;
    }
}

private static void merge(int[] array, int left, int mid, int right) {
    int[] tmp = new int[right-left+1];
    int k = 0;
    int s1 = left;
    int e1 = mid;
    int s2 = mid+1;
    int e2 = right;

    while(s1 <= e1 &&  s2 <= e2){
        if(array[s1] <= array[s2]){
            tmp[k++] = array[s1++];
        }else {
            tmp[k++] = array[s2++];
        }
    }

    while(s1 <= e1){
        tmp[k++] = array[s1++];
    }

    while(s2 <= e2){
        tmp[k++] = array[s2++];
    }
    //可以保证tmp数组是有序的
    for (int i = 0; i < k; i++) {
        array[i+left] = tmp[i];
    }
}

计数排序

非基于比较的排序

还有桶排序， 基数排序，感兴趣可以了解一下

使用场景：集中在某个范围内的一组数据

 步骤：

  1. 根据数据的个数来创建数组
  2. 把对应元素出现的个数给到对应的位置，记录出现的次数
  3. 根据记录的次数，依次输出元素

代码如下 ：

public static void countSort(int[] array){

    //1.找最大值 和 最小值 来确定 计数数组的大小
    int maxVal = array[0];
    int minVal = array[0];
    for (int i = 1; i < array.length; i++) {
        if(array[i] > maxVal){
            maxVal = array[i];
        }
        if(array[i] < minVal){
            minVal = array[i];
        }
    }
    int len = maxVal - minVal + 1;
    int[] count = new int[len];

    //2.遍历原来的数组array， 把每个元素 放到对应的计数数组中 进行比较
    for (int i = 0; i < array.length; i++) {
        int index = array[i];
        count[index-minVal]++;
    }

    //3.依次 遍历计数数组
    int index = 0;
    for (int i = 0; i < count.length; i++) {
        while(count[i] != 0){
            array[index] = i+minVal;
            index++;
            count[i]--;
        }
    }
}

本站资源均来自互联网，仅供研究学习，禁止违法使用和商用，产生法律纠纷本站概不负责！如果侵犯了您的权益请与我们联系！

转载请注明出处： 免费源码网-免费的源码资源网站 » Java实现八种排序

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

 发表
评论 返回
顶部