算法排序专题

矫情吗；* 2023-07-18 03:00 49阅读 0赞

### 排序专题 ###

*  归并排序（nlogn）
 *  堆排（nlogn）
 *  快排（nlogn）
 *  GIF动图演示各种排序算法

# 归并排序（nlogn） #

> 比如\[2,1\]。【分割】对左边拆分成2，此时l=r，2放进新数组，对右边拆分成1，此时l=r，1放进新数组。【合并】1.左数组长度=右数组长度，那边元素小，那边就放元素到合并数组，并往后继续取元素比较。直到没有元素可取为止  
> 2.左数组长度 >右数组长度,左边数组依次将元素放入到合并数组  
> 3.右数组长度 >左数组长度,右边数组依次将元素放入到合并数组

public class MergeSort {    
        public static int[] mergeSort(int[] nums, int l, int h) { 
            if (l == h)
                return new int[] {  nums[l] };
             // int mid=(l+r)>>>2; 它会出现栈溢出
            int mid=(l+r)>>>1;    //往低位移1位是/2，移2位是/4
            int[] leftArr = mergeSort(nums, l, mid); //左有序数组
            int[] rightArr = mergeSort(nums, mid + 1, h); //右有序数组
            int[] newNum = new int[leftArr.length + rightArr.length]; //新有序数组
             
            int m = 0, i = 0, j = 0; 
            while (i < leftArr.length && j < rightArr.length) { 
                newNum[m++] = leftArr[i] < rightArr[j] ? leftArr[i++] : rightArr[j++];
            }
            while (i < leftArr.length)
                newNum[m++] = leftArr[i++];
            while (j < rightArr.length)
                newNum[m++] = rightArr[j++];
            return newNum;
        }
        public static void main(String[] args) { 
            int[] nums = new int[] {  9, 8, 7, 6, 5, 4, 3, 2, 10 };
            int[] newNums = mergeSort(nums, 0, nums.length - 1);
            for (int x : newNums) { 
                System.out.println(x);
            }
        }
    }

# 堆排（nlogn） #

1.  堆化【max!=i 就一直递归，因为随着父节点的切换，其子树始终维持大顶堆的规则】
2.  建堆【i=(n-1)/2; i–】
3.  排序【i=n-1;i–】  
    序号是按照完全二叉树来弄得【比如：\[1，2，3，4，5\] 其对应的左儿子：2*i+1，右儿子：2*i+2;】

public class HeapSortTest { 
        @Test
        public void run()
        { 
            int a[]={ 5,3,7,2,4,6};
            heap_sort(a,6);
            for (int b:a){ 
                System.out.println(b);
            }
        }
        /** * 从下往上，从右往左，一次找到父节点，然后进行堆化 */
        void build_heap(int tree[],int n){ 
            int last_node=n-1;
            int parent=(last_node-1)/2;
            int i;
            for(i=parent;i>=0;i--){ 
                heapify(tree,n,i);
            }
        }
        //heapify----堆化，堆调整，的意思
        void heapify(int tree[],int n,int i){ 
            /** * 是否满足大顶堆的顺序，逆序则交换 */
            if (i>=n){ 
                return;
            }
            int c1=2*i+1;
            int c2=2*i+2;
            int max=i;
            if (c1<n&&tree[c1]>tree[max]){ 
                max=c1;
            }
            if (c2<n&&tree[c2]>tree[max]){ 
                max=c2;
            }
            if (max!=i){ 
                swap(tree,max,i);
                heapify(tree,n,max);
            }
        }
        void swap(int tree[],int i,int j){ 
            int temp=tree[i];
            tree[i]=tree[j];
            tree[j]=temp;
        }
        void heap_sort(int tree[],int n){ 
            build_heap(tree,n);
            int i;
            for (i=n-1;i>=0;i--){ 
                swap(tree,i,0);  //交换+剪短
                heapify(tree,i,0);  //调整堆，使堆常保持大顶堆的姿态。
            }
        }
    }
    //输出结果：2,3,4,5,6,7

![在这里插入图片描述][aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy8xOTQwMzE3LTljMzdiNGJlMWI3Yzk2ZDEuZ2lm]  
![在这里插入图片描述][202004150640297.png]  
![在这里插入图片描述][2020041506403794.png]  
![在这里插入图片描述][20200415064044775.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDYzMTQx_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDYzMTQx_size_16_color_FFFFFF_t_70 1]

# 快排（nlogn） #

> if（左右指针参数合法&&左指针<右指针）\{ //否则直接结束  
> 首先定义5个变量，low和start记录左指针位置，high和end记录右指针位置，base记录基数值  
> 然后遍历数组【只要左指针<右指针，就一直遍历数组】，假设每轮都选定数组首元素做为基数。先将右指针从右往左移，遇到比基数小于或等于的数就停下来（或左指针和右指针相遇），交换他和基数的位置。接着将左指针从左往右移，遇到比基数大于或等于的就停下来（或左指针和右指针相遇），交换当前它和右指针的位置。最后将基数填到当前右指针的位置处（基数归位）。  
> 然后再递归对左边的进行排序，再递归的对右边的进行排序。  
> ==注意：==while里面的判断条件和我们日常的描述是相反的

> 双指针：每次递归选数组首元素作为基数，先从后往前遇到比基数小的，就停下来交换位置(移到最前面)，然后从前往后遇到比基数大的，就停下来交换位置(移到最后面)，接着如此（移到次后面，次前面），知道指针相遇，再把基数赋值到该位置。进入下一次递归（对左边数组来一下，对右边数组来一下）  
> 321进行自然排序

代码如下：

public static void quicksort(int arr[], int left, int right) { 
            if (left >= 0 && right <= arr.length - 1 && left < right) { 
                int low = left;
                int hight = right;
                int base = arr[left];   //因为我选的哨兵位是最左边，所以这就决定了首次进行逆序交换的一定是比基数小的，也就是说 必须先交换右边的，才能再交换左边的。
                while (left < right) { 
                    while (left < right && arr[right] >= base) right--;
                    arr[left] = arr[right];
                    while (left < right && arr[left] <= base) left++;
                    arr[right] = arr[left];
                }
                arr[right] = base;
                quicksort(arr, low, left - 1);
                quicksort(arr, left + 1, hight);
            }
    
        }
    
    
    //测试
    public static void main(String[] args) { 
                int[] nums = new int[] {  9, 8, 7, 6, 5, 4, 3, 2, 10 };
                int[]  a=quicksort(nums,0,nums.length-1);
                for (int x:a){ 
                    System.out.println(x);
                }
            }

![在这里插入图片描述][20150805112443608]

# GIF动图演示各种排序算法 #

[GIF动图演示各种排序算法][GIF]

[aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy8xOTQwMzE3LTljMzdiNGJlMWI3Yzk2ZDEuZ2lm]: /images/20230528/47bf7777600c43488f107dc630111670.png
[202004150640297.png]: /images/20230528/994f2d63e9884ecf82aedf4080491dea.png
[2020041506403794.png]: /images/20230528/b3e17938c02442b4bcd344ec6acaaaea.png
[20200415064044775.png]: /images/20230528/d9e64759fd63471ebeb866db9043d8c8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDYzMTQx_size_16_color_FFFFFF_t_70]: /images/20230528/38608145de244876b3e04157d763b7e2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDYzMTQx_size_16_color_FFFFFF_t_70 1]: /images/20230528/d3b49d1fa4474f66a05fd8a46b1f4198.png
[20150805112443608]: /images/20230528/b3544c5207634bbfbc1a84259b5843f7.png
[GIF]: https://blog.csdn.net/u011464124/article/details/70054204