排序算法java实现-创新互联

思路：

1. 从左边选一个目标元素target。 i = left， j = right；
2. 从j处右往左遍历，直到找到一个比 target 小的元素；然后从i处左往右遍历，直到找到一个比target 大的元素；
3. 此时a[j]< target; a[i] >target； 我们将二者互换；
4. 继续遍历，由于步骤3已经互换元素，此时的a[j] >target, a[i]< target;
   我们继续遍历，重复步骤2 ，3直到i， j相遇
5. 相遇时，i处之前的元素小于target，i处之后元素均大于target；a[i] 小于target；
6. 我们将target 和a[i] 互换。i处之前的元素小于a[i]，i处之后元素均大于a[i]；
7. 递归地处理左区间和右区间

public static void quickSort(int[] arr) {//        int[] arr = {3,1,4,7,2,9,8};
        doQuickSort(arr, 0, arr.length-1);
    }
    private static void doQuickSort(int[] arr, int left, int right) {if(left >= right) return;
        int base = arr[left];
        int i = left,j = right;
        while (i< j) {while (arr[j] >= base && i< j) {j--;
            }
            while (arr[i]<= base && i< j) i++;
            if(i< j) {int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        arr[left] = arr[i];
        arr[i] = base;
        doQuickSort(arr, left, i-1);
        doQuickSort(arr, i+1, right);
    }

public static void divideSort(int[] arr, int left, int right) {if(left >= right)
            return;
        //取中间索引
        int mid = (left + right)/2;
        //分别排序
        divideSort(arr,left,mid);
        divideSort(arr,mid+1,right);
        //合并结果
        merge(arr,left,mid,right);
    }
    public static void merge(int[] arr,int left,int mid,int right) {int[] temp = new int[right-left+1];//建立临时数组
        int i = left;
        int j = mid + 1;//指向两个数组的起始位置
        int k = 0;//指向临时数组的起始位置
        while(i<= mid && j<= right) {if(arr[i] >= arr[j]) {//将更小的arr[j]放进临时数组中
                temp[k++] = arr[j++];
            }else {//将更小的arr[i]放进临时数组中
                temp[k++] = arr[i++];
            }
        }
        while(i<= mid) {//前一个数组还有剩余
            temp[k++] = arr[i++];
        }
        while(j<= right) {//前一个数组还有剩余
            temp[k++] = arr[j++];
        }
        //将临时数组中的值更新到原始数组中
        for(int p = 0;p< temp.length;p ++) {arr[left+p] = temp[p];
        }
    }

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧