自学内容网 自学内容网

“从零开始学排序:简单易懂的算法指南“

 “一辈人有一辈人要做的事!!!”

这一期的节目呢,是关于排序的内容,相信大家对此一定很熟悉吧!

排序:

排序是将一组元素按照一定的规则或标准进行组织和排列的过程。

冒泡排序:

冒泡排序是一种简单的排序算法,主要用于数组或列表中的元素进行排序。它通过重复比较相邻的元素并交换他们的顺序来工作。从而将未排序的元素逐渐“冒泡”到列表的末尾。

工作原理:
  1. 从数组的开始位置,依次比较相邻的两个元素。
  2. 如果前一个元素大于后一个元素,则交换它们的位置。
  3. 这一过程会将最大的元素移动到数组的末尾。
  4. 对剩余的未排序元素重复以上过程,直到所有元素都排序完成

第一趟排序之后,该数组中的最大值就到达了该到的位置,接下来按照上述方法进行第二趟排序,第三趟排序…………直到全部都排好序。那么我们一共要进行多少趟排序呢?当数组中只剩一个数没有排时,此时它的位置就无须改动,因为其他的数都到达了自己相应的位置。所以我们只需排 (N-1)次就可以了, 那么在进去的第一趟应该怎么进行上述的逻辑呢?里面是两两数从数组下标0一直比较到数组末尾,所以我们可以循环的按照规则去比较,则可写出以下代码:

 public static void BubbleSort(int[] array) {
        int n = array.length;
        //趟数
        for(int i = 0;i < n-1;i++) {
            for(int j = 0;j < n-1;j++) {
                if(array[j] > array[j+1]) {
                    swap(i,j,array);
                }
            }
        }
    }

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

也是全部排好序了 。此时我们可以发现,其实 j 下标不用每次都到数组的末尾,因为我们的一趟排序下来之后,数组中最大的那个数就到达了它相应的位置了,所以我们可以根据趟数的增加来减少我们的比较趟数!那如果此时是一个已经排好序的数组呢,此时我们也可以做一些相应的优化!

public static void BubbleSort(int[] array) {
        int n = array.length;
        boolean flg = false;
        //趟数
        for(int i = 0;i < n-1;i++) {
            for(int j = 0;j < n-1-i;j++) {
                if(array[j] > array[j+1]) {
                    swap(i,j,array);
                    flg = true;
                }
            }
            if(!flg) {
                break;
            }
        }
    }

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

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

空间复杂度:O(1)

稳定性:稳定


直接选择排序: 

直接选择排序(Selection Sort)是一种简单的排序算法,主要思想是不断选择未排序部分的最小(或最大)元素,并将其放到已排序部分的末尾。

算法步骤:
  1. 从未排序的数组中找到最小的元素。
  2. 将该最小元素与未排序部分的第一个元素交换位置。
  3. 继续对未排序部分执行步骤1和2,直到整个数组都被排序。

第一次排序之后,最小值就到了数组下标为0的位置了(到达了它在数组中对应的位置),此时我们再从数组下标为1的位置开始往后找,每一次找到未处理中的最小值,直到遍历完。

public static void SelectSort(int[] array) {
        for(int left = 0; left < array.length;left++) {
            //先假设一个最小值下标
            int minIndex = left;
            for(int j = left+1;j < array.length;j++) {
                if(array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            //交换
            swap(left,minIndex,array);
        }
    }

上面的是找一边,那么我们也可以找两边呀,直接定义两个变量,一个是最小值的下标 minIndex,

一个是最大值的下标 maxIndex。每次找到后,交换到相应的位置,类似于上面的!

 

 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(left,minIndex,array);
            swap(right,maxIndex,array);

            //缩小范围
            left++;
            right--;
        }

结果显示也是排序对的,那么这个代码真的就对了吗?是否还存在问题呢?我们一起来看看最大值在下标为0的结果展示:

最大值在数组下标为0的位置时,结果是错的,那么为什么会错呢,我们一起来跟着代码逻辑来分析分析: 

 

所以再进行交换完minIndex left时,我们需要 maxIndex = minIndex;

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(left,minIndex,array);
            //先进行判断
            if(maxIndex == left) {
              maxIndex = minIndex;
            }
            swap(right,maxIndex,array);

            //缩小范围
            left++;
            right--;
        }

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

空间复杂度:O(1)

稳定性:不稳定


 直接插入排序:

直接插入排序(Insertion Sort)是一种简单且直观的排序算法,适用于小规模的数据。其基本思想是通过将新元素插入到已排序的部分中来构建排序序列。

算法步骤:
  1. 假设第一个元素已经被排序,从第二个元素开始。
  2. 取出当前元素(称为“key”),与已经排序的元素进行比较。
  3. 找到合适的位置,将当前元素插入到已排序部分,并将其他元素向后移动以腾出空间。
  4. 重复步骤 2 和 3,直到所有元素都被插入到已排序部分。

 如果是tmp大于array[j]时,就不用做处理!

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 {
                    break;
                }
            }
            //此时就找到了对应的位置了。
            array[j+1] = tmp;
        }
    }

 时间复杂度:

  • 最好情况:O(n)(当输入数据已基本有序时)
  • 最坏情况:O(n^2)(当输入数据完全逆序时)

空间复杂度:O(1)

稳定性:稳定


希尔排序:

希尔排序(Shell Sort)是一种基于插入排序的排序算法,通过将原始数组分成若干个子数组,对各个子数组进行插入排序,从而最终实现整个数组的排序。希尔排序的优势在于它在移动元素时可以跳过一定的距离,从而减少了整体的比较次数。

算法步骤:
  1. 选择一个增量(gap),通常先将数组分成多个子数组,每个子数组的元素间隔为 gap
  2. 对每个子数组进行插入排序。
  3. 随着算法的进行,逐渐减小 gap 值,直到 gap 变为 1,此时相当于对整个数组进行插入排序。
  4. 当 gap 为 1 时,整个数组将被完全排序。

上面的图当中,我们可以发现,根据gap的减小,数据会越来越趋于有序,当gap为1时,此时就相当于对一整个数组进行插入排序。

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

    private static void Shell(int gap, int[] array) {
        //i++ 子数组交替着去执行插入排序
        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 {
                    break;
                }
            }

            array[j+gap] = tmp;
        }
    }

时间复杂度: 

  • 最好情况:O(n log n)
  • 平均情况:O(n^1.3)(具体取决于增量序列的选择)
  • 最坏情况:O(n^2)

空间复杂度:O(1)

稳定性:不稳定


堆排序:

堆排序(Heap Sort)是一种基于比较的排序算法,它利用堆的数据结构进行排序。

算法步骤:
  1. 构建最大堆:将无序数组构建成最大堆。这个步骤会将最大元素放在堆的根节点(数组的第一个位置)。
  2. 排序
    • 将堆顶元素(最大值)与堆的最后一个元素交换,然后减少堆的大小(排除该元素)。
    • 对新的堆根节点进行堆化(Heapify),使其重新符合最大堆性质。
    • 重复上述过程,直到堆的大小为1。

对于堆排序呢,我在前面的文章中有着详细的过程,这里呢我就只展示其代码了。

public static void HeapSort(int[] array) {
        //先创建大根堆
        CreateBigHeap(array);
        int endIndex = array.length-1;

        while(endIndex >= 0) {
            swap(0,endIndex,array);
            siftDown(array,0,endIndex);
            endIndex--;
        }
    }

    private static void CreateBigHeap(int[] array) {
        for(int parent = (array.length-1-1)/2;parent >= 0;parent--) {
            siftDown(array,parent,array.length);
        }
    }

    //向下调整
    private static void siftDown(int[] array, int parent, int end) {
        int child = 2*parent+1;
        while( child < end ) {
            if(child+1 < end && array[child] < array[child+1] ) {
                child++;
            }

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

快速排序:

快速排序(Quick Sort)是一种高效的分治排序算法,采用了“随机选择”的思想来将数组分为两部分,并递归地对这两部分进行排序。

算法步骤:
  1. 选择基准:从数组中选择一个元素作为基准。
  2. 分区:将数组重新排列,使得所有小于基准的元素位于基准的左侧,所有大于基准的元素位于基准的右侧。基准元素最终在其正确的位置上。
  3. 递归排序:递归地对基准左侧和右侧的子数组进行快速排序。

 那么此时45的位置就是它最后相应的位置了,因为前面的数据都比他小,后面的数据都比他大。然后我们开始递归的去左侧基准和去右侧基准。

那么对于右边部分的情况来说,也是如此,只是右边部分的范围是[par+1,right]:

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

    private static void Quick(int left, int right, int[] array) {
        if(left >= right) {
            return ;
        }

        int par = HarePartition(left,right,array);

        Quick(left,par-1,array);
        Quick(par+1,right,array);
    }


    private static int HarePartition(int left, int right, int[] array) {
        int i = left;
        int tmp = array[left];
        while(left < right) {
            //这里是先从右边,不然可能无法正确排序
            // array[right] >= tmp 这里的 = 不能没有,否则会可能出现死循环的情况。
            while(left < right && array[right] >= tmp) {
                right--;
            }

            while(left < right && array[left] <= tmp) {
                left++;
            }
            swap(left,right,array);
        }
        swap(i,left,array);

        return left;
    }

 

上述的 int par = HarePartition(left,right,array)的过程中,使用到的是Hare法,我们还可以用另外中方法--“挖坑法”。

 

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

        while(left < right) {
            //右边
            while(left < right && array[right] >= tmp) {
                right--;
            }
            array[left] = array[right];

            //左边
            while(left < right && array[left] <= tmp) {
                left++;
            }
            array[right] = array[left];
        }
        array[left] = tmp;
        return left;

    }

对于递归的方法,我们已经说完了,接下来我们就来说一说,快速排序的非递归方法:

那么对于非递归的快速排序,我们应该怎么去做呢?我们可以使用一种数据结构--栈,相信大家都对栈有所了解吧“先进后出”,当然使用队列也是可以的,这里我就一栈为例子了。我们在递归思想中,每次去递归,都是传新的 left 和 right,那么我们在非递归中,我们就用栈来维护新的left 和 right,在恰当的时机去出栈和进栈!

 

public static void QuickSortNor(int[] array) {
        Stack<Integer> stack = new Stack<>();
        int left = 0;
        int right = array.length-1;
        int par = HarePartition(left,right,array);

        //进栈时,判断一下
        if(left + 1 < par) {
            stack.push(left);
            stack.push(par-1);
        }

        //进栈时,判断一下
        if(par + 1 < right) {
            stack.push(par+1);
            stack.push(right);
        }

        while(!stack.isEmpty()) {
            //进行出栈,录入新的left 和 right
            right = stack.pop();
            left = stack.pop();

            par = HarePartition(left,right,array);
            if(left + 1 < par) {
                stack.push(left);
                stack.push(par-1);
            }
            if(par + 1 < right) {
                stack.push(par+1);
                stack.push(right);
            }
        }
    }

 当然你也可以使用队列来完成!

时间复杂度:O(N * log N)

空间复杂度:最坏的情况下:O(N)   最好的情况:O(N* log N)

稳定性:不稳定


归并排序:

归并排序(Merge Sort)是一种高效的比较排序算法,采用分治法(Divide and Conquer)来排序。其基本思想是将数组分成两半,递归地对这两部分进行排序,然后再将两个已排序的部分合并成一个完整的已排序数组。

算法步骤:
  1. 分割:将数组从中间分成两部分。
  2. 递归排序:对每个部分递归地应用归并排序。
  3. 合并:将两个已排序的子数组合并成一个已排序的数组。

 

但是可能左边部分的元素个数和右边的元素个数不一样,那么此时数组空间大的那边就还会剩有元素,此时就直接补在tmp数组后面就行了,因为是排好序的!

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

    private static void MergeFun(int left, int right, int[] array) {
        if(left >= right) {
            return ;
        }

        int mid = (right+left)/2;

        //分
        MergeFun(0,mid,array);
        MergeFun(mid+1,right,array);

        //合并
        Merge(left,mid,right,array);
    }

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

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

        //检查剩余情况
        while(s1 <= mid) {
            tmp[k++] = array[s1++];
        }

        //检查剩余情况
        while(s2 <= right) {
            tmp[k++] = array[s2++];
        }

        //拷贝回原数组
        for(int i = 0;i < k;i++) {
            array[left+i] = tmp[i];
        }
    }

在拷贝回原数组的时候,一定要小心,不能直接是array[i] = tmp[k]。可能传过来的left下标是后面的,一旦写成 array[i] = tmp[k],那么就会从下标为0开始填充着走。

上述是递归的写法,下面就来说一说非递归的方法:

上面是先分之后,才开始合并的。那么我们这里就直接把它看成每个单个是已经分好了的,此时我们直接开始进行合并。

 public static void MergeSortNor(int[] array) {
        int gap = 1;

        while(gap < array.length) {
            for(int i = 0;i < array.length; i = i+2*gap) {
                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(left,mid,right,array);
            }

            gap *= 2;
        }
    }

时间复杂度:O(N* log N)

空间复杂度:O(N)

稳定性:稳定 


排序算法还有很多,感兴趣的铁汁们,可以去了解其他的有趣的排序算法!

“希望读者能在评论区分享他们最喜欢的排序算法以及实践中的经验。不同的场景下,算法的表现可能完全不同,让我们一起讨论这些有趣的话题!”

我们下一期再见!!!


原文地址:https://blog.csdn.net/2302_77675796/article/details/142618749

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!