美文网首页android基本功其他
快速排序-左右指针法-java

快速排序-左右指针法-java

作者: 减瘦了的胖子 | 来源:发表于2018-11-04 12:48 被阅读120次

    左右指针法容易出现问题的地方是一趟快速排序相遇时的处理方式
    如果参考在末尾,要先从左走
    如果参考在数组头部,要先从右走

    参考在数组头部,要先从右走

        private static int partition(int[] array, int left, int right) {
            int key = array[left];
            int index = left;
            while (left < right) {
    
                while (left < right && array[right] <= key) {
                    --right;
                }
    
                while (left < right && array[left] >= key) {
                    ++left;
                }
    
                swap(array, left, right);
            }
            swap(array, right, index);
            return right;
        }
    
        private static void swap(int[] cost, int i, int j) {
            int temp = cost[i];
            cost[i] = cost[j];
            cost[j] = temp;
        }
    

    参考在末尾,要先从左走

        private static int partition2(int[] array, int left, int right) {
            int key = array[right];
            int index = right;
            while (left < right) {
    
                while (left < right && array[left] <= key) {
                    ++left;
                }
    
                while (left < right && array[right] >= key) {
                    --right;
                }
    
                swap(array, left, right);
            }
            swap(array, left, index);
            return left;
        }
    

    参考:
    https://www.jianshu.com/p/bb41e3be09ba

    相关文章

      网友评论

        本文标题:快速排序-左右指针法-java

        本文链接:https://www.haomeiwen.com/subject/afprxqtx.html