【Java---数据结构】排序算法

• 非递归实现快速排序需要借助栈来实现。
• 先在待排序序列中找一次基准，将左边界的下标、基准左边的下标、基准右边的下标，右边界的下标依次入栈。
• 下标入栈时要判断基准值左右序列是否有两个以上的元素。如果有，将序列的左右边界下标入栈。
• 当栈不为空时d出栈顶的两个元素，先出栈的元素放到右边（right = stack.pop();），后出栈的元素放到左边（left = stack.pop();）。元素出栈后重新找基准值的位置，并再次入栈。
• 重复执行上面的 *** 作，直到栈为空时结束。

🌊代码实现

//元素交换
public static void swap(int[] array,int index1,int index2){
    int tmp = array[index1];
    array[index1] = array[index2];
    array[index2] = tmp;
}

/**
 * 挖坑法找基准：使用三数取中法进行优化
 * 找三个数中，中间大小的值的下标
 * @param array 待排序序列
 * @param left 数组左边界
 * @param right 数组右边界
 * @return 然后三个数中，中间大小值的下标
 */
public static int findmidValInde(int[] array,int left,int right){
    int mid = left + ((right-left)>>>1); //int mid = (left+right)/2;
        if(array[left]>array[right]){
            if(array[mid] > array[left]){
                swap(array,left,left);
            }else if(array[mid] < array[right]){
                swap(array,right,left);
            }else {
                swap(array,mid,left);
            }
        }else{
            if(array[mid] < array[left]){
                swap(array,left,left);
            }else if(array[mid] > array[right]){
                swap(array,right,left);
            }else {
                swap(array,mid,left);
            }
        }
    int tmp = array[left];
    while (left=tmp){
            right--;
        }
        //right 指向的值小于tmp的值，将end指向的元素存放到“坑”中（right下标处为“新挖的坑”）
        array[left] = array[right];
        //从首元素开始与基准值进行比较，遇到比基准值小的元素 left 就向后移动
        while (left stack = new Stack<>();
    int left = 0;
    int right = array.length-1;
    //找基准
    int pivot = findmidValInde(array,left,right);
    if(left+1pivot){
        //基准右边至少有两个元素
        stack.push(pivot+1);
        stack.push(right);
    }
    while (!stack.isEmpty()){
        right = stack.pop();
        left = stack.pop();
        pivot = findmidValInde(array,left,right);
        if(left+1pivot){
            stack.push(pivot+1);
            stack.push(right);
        }
    }
}

📔优化前

📔 优化后

• 在了解归并排序前，先做一个道题：将两个有序数组合并成一个有序的数组。

• 有两个有序的数组，第一个数组 array1 的长度为len1，第二个数组 array2 的长度为 len2，创建一个大小为 len1+len2 的新数组存放合并后的数据。
• 比较两数组的元素按从小到大的顺序将数据拷贝到新的数组中。
• 如果其中有一个数组遍历完，就将另一个未遍历完的数组中的元素拷贝到新数组中。

 🌊代码实现

//合并两个有序数组
public static int[] mergeArray(int[] array1,int[] array2){
    int s1 = 0;
    int s2 = 0;
    int index = 0;
    int e1 = array1.length-1;
    int e2 = array2.length-1;
    int[] newArray = new int[array1.length+array2.length];
   while (s1<=e1 && s2<=e2){
       if(array1[s1]>array2[s2]){
           newArray[index++] = array2[s2++];
       }else {
           newArray[index++] = array1[s1++];
       }
   }
   while (s1<=e1){
       newArray[index++] = array1[s1++];
   }
   while (s2<=e2){
       newArray[index++] = array2[s2++];
   }
   return newArray;
}

• 归并排序（MERGE-SORT）是建立在归并 *** 作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。
• 将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
• 若将两个有序表合并成一个有序表，称为二路归并。

• 归并排序核心思想是合并有序数组。
• 首先将数组分解成一个一个的元素，并进行分组，每组一个元素。此时每组的元素全部是有序（因为只有一个元素）。
• 然后两两一组进行有序合并，合并后的数组也是有序数组，最后将合并的数组继续与其他合并的数组合并，直到完全合并为止。
• 分组后两两一组进行合并，第一组序列左边界为left，右边界为 mid， 第二组序列的左边界为 mid+1，右边界为 right，则合并后新数组的长度为 right-left+1。
• 对于数组的分解再合并，最常见的思路就是递归。

🌊代码实现

/**
 * 归并排序
 * 时间复杂度：O(N*logN)
 * 空间复杂度：O(N)
 * 稳定性：稳定
 *如果 array[s1]>=array[s2] 不取等号，就是不稳定的
 * @param array
 */
public static void mergeSort(int[] array){
    mergeSortInternal(array,0,array.length-1);
}
public static void mergeSortInternal(int[] array,int left,int right){
    if(left>=right){
        return;
    }
    int mid = left+((right-left)>>>1);
    //分解左边
    mergeSortInternal(array,left,mid);
    //分解右边
    mergeSortInternal(array,mid+1,right);
    //合并
    merge(array,left,mid,right);
}
public static void merge(int[] array,int left,int mid,int right){
    int s1 = left;
    int s2 = mid+1;
    int e1 = mid;
    int e2 = right;
    int index = 0;
    int[] newArray = new int[right-left+1];
    while (s1<=e1 && s2<=e2){
        if(array[s1]>=array[s2]){
            newArray[index++] = array[s2++];
        }else {
            newArray[index++] = array[s1++];
        }
    }
    while (s1<=e1){
        newArray[index++] = array[s1++];
    }
    while (s2<=e2){
        newArray[index++] = array[s2++];
    }
    for (int i = 0; i < index; i++) {
        array[i+left] = newArray[i];
    }
}

• 将数组进行分组排序，需要确定每一组的左边界，中间下标，右边界。确定好下标后就可以对每一组进行合并。
• 每组的左边界为 left，每一组的组数为 nums，则 mid = left + nums -1，right = mid + nums。
• 定义变量 i 对数组进行遍历。因为每遍历完一组数据，就要重新遍历下一组，所以 left = i，按照上面的公式就可以计算出每组中 mid 与 right 的值。
• 每组组数为 nums（初始为1组），合并后，除了最后一组的元素个数不能保证为 2*nums，其他组的元素个数均为2*nums，所以完成一组合并后（一趟合并），num = 2*num。
• 因为每次合并两组数据，每遍历完一次就完成一组数据的合并，所以 i 的增量为 2*nums。
• 对每一组进行合并时都需要保证调整后的 mid 与 right 不能越界。如果越界，则需要调整为指向待排序序列的最后一个元素。
• 每次合并数组前，需要保证每组元素个数 nums 小于待排序序列长度，如果满足此条件就继续合并，不满足则表示已完成排序。

🌊代码实现

/**
 *合并有序序列
 * @param array 待合并的序列
 * @param left 每组序列的左边界
 * @param mid 每组序列的中间下标
 * @param right 每组序列的右边界
 */
public static void merge(int[] array,int left,int mid,int right){
    int s1 = left;
    int s2 = mid+1;
    int e1 = mid;
    int e2 = right;
    int index = 0;
    int[] newArray = new int[right-left+1];
    while (s1<=e1 && s2<=e2){
        if(array[s1]>=array[s2]){
            newArray[index++] = array[s2++];
        }else {
            newArray[index++] = array[s1++];
        }
    }
    while (s1<=e1){
        newArray[index++] = array[s1++];
    }
    while (s2<=e2){
        newArray[index++] = array[s2++];
    }
    for (int i = 0; i < index; i++) {
        array[i+left] = newArray[i];
    }
}

/**
 * 非递归实现归并排序
 * @param array 待排序序列
 */
public static void mergeSort(int[] array){
    int nums = 1;//每组数据的个数
    while (nums<=array.length){
        //数组没都需要遍历，确定归并的区间
        for(int i=0;i=array.length){
                mid = array.length-1;
            }
            int right = mid+nums;
            //防止越界
            if(right>=array.length){
                right = array.length-1;
            }
            //下标确定后，进行合并
            merge(array,left,mid,right);
        }
        nums*=2;
    }
}