быстрая сортировка

Алгоритм сортировки

Быстрая сортировка — еще одно типичное применение идеи «разделяй и властвуй» в алгоритме сортировки. Быстрая сортировка использует стратегию «разделяй и властвуй», чтобы разделить список на два подсписка. Конкретный алгоритм описывается следующим образом:

  • Выберите элемент из последовательности, называемый «стержнем»;
  • Измените порядок последовательности: все элементы, меньшие эталонного значения, помещаются перед эталонным значением, а все элементы, превышающие эталонное значение, помещаются в конце эталонного значения (одинаковые числа могут идти с обеих сторон). После выхода из раздела эталон находится в середине последовательности. Это называется операцией раздела;
  • Рекурсивно отсортируйте подмассивы элементов меньше эталонного значения и подмассивы элементов больше эталонного значения.

временная сложность

В среднем для сортировки n элементов требуется Ο(nlogn) сравнений. В худшем случае требуется 0(n2) сравнений, но это не является обычным явлением. На самом деле быстрая сортировка обычно значительно быстрее других алгоритмов Ο(nlogn), потому что ее внутренний цикл может быть эффективно реализован на большинстве архитектур.

Наихудшим случаем для быстрой сортировки является O(n²), например быстрая сортировка для последовательных массивов. Но его амортизированное ожидаемое время равно O(nlogn), а постоянный множитель, неявный в обозначении O(nlogn), мал, намного меньше, чем сортировка слиянием, сложность которой стабильно равна O(nlogn). Поэтому для большинства случайных последовательностей со слабым порядком быстрая сортировка всегда лучше, чемСортировка слиянием.

Классическая быстрая очередь

код

public static void quickSort1(int[] arr){
        if (arr == null || arr.length <2){
            return;
        }
        process1(arr,0,arr.length-1);
    }

    public static void process1(int[] arr, int L, int R){
        if (L>=R){
            return;
        }
        int M =partition(arr,L,R);
        process1(arr,L,M-1);
        process1(arr,M,R);

    }

    private static int partition(int[] arr,int L,int R) {
        if (L>R){
            return -1;
        }
        if (L ==R){
            return L;
        }
        int lessEqual = L-1;//小于等于的位置
        int index = L;//当前位置
        while (index<R){
            if (arr[index]<=arr[R]){
                //如果当前位置的数据小于等于 目标数据 ，则把当前位置的数据和 小于等于位置的的下一个位置进行交换
                //同时 小于等于位置往下移动一位
                swap(arr,index,++lessEqual);
            }
            index++; //当前位置往后移动一位
        }
        //最后，小于等于位置和 目标数据进行交换
        swap(arr,++lessEqual,R);
        return lessEqual;

    }

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

Схема части цикла цикла while кода

png.png

Оптимизированная версия быстрой сортировки

Достоинства: Разделен на три части.

код

public static void quickSort2(int[] arr){
        if (arr == null || arr.length<2){
            return;
        }
        process2(arr,0,arr.length-1);
    }

    private static void process2(int[] arr, int L, int R) {
        if (L>=R){
            return;
        }
        //小于等于目标区域
        int[] equalArea = netherLandsFlag(arr,L,R);
        process2(arr,L,equalArea[0]-1);
        process2(arr,equalArea[1]+1,R);

    }

    private static int[] netherLandsFlag(int[] arr, int L, int R) {
        if (L>R){
            return new int[]{-1,-1};
        }
        if (L == R){
            return new int[]{L,R};
        }
        int less = L-1;//小于区域 的右边界
        int more = R;//大于区域的 左边界
        int index = L;//当前位置
        while (index<more){
            if (arr[index] == arr[R]){
                index++;
            }else if (arr[index] < arr[R]){
//                swap(arr,index,less+1);
                //less++
//                index++;
                //优化一下
                swap(arr,index++,++less);
            }else {
                //此时index 不向下移动，因为换过来的数还没有看
                swap(arr,index,--more);
            }
        }
        swap(arr,more,R);//  <[R] =[R] >[R]
        return new int[]{less+1,more};
    }

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

int more = R; // больше левой границы области Почему граница больше площади R, потому что число в позиции R является целевым числом для сравнения, эта позиция зарезервирована, а R-1 левая граница больше R В начале сравнение номера цели выполняется в позиции [L--R-1], поэтому граница имеет вид: L-1)L....R-1(R

диаграмма

image.png

Улучшенная случайная быстрая сортировка

Классическая быстрая сортировка всегда указывает последний элемент массива или определенную часть в качестве эталонного значения, а случайная быстрая сортировка указывает в качестве эталонного значения случайное значение в массиве или определенную его часть.

Преимущество этого заключается в том, чтобы избежать наихудшего случая быстрой сортировки, который составляет O (n²).

диаграмма

quicksort.gif

код

 private static void quickSort3(int[] arr){
        if (arr ==null || arr.length<2){
            return;
        }
        process3(arr,0,arr.length-1);
    }

    private static void process3(int[] arr, int L, int R) {
        if (L>=R){
            return;
        }
        //随机选择一个数和目标数进行交换
        swap(arr,L+(int)(Math.random() *(R-L+1)),R);
        int[] equalArea = netherLandsFlag(arr,L,R);
        process3(arr,L,equalArea[0]-1);
        process3(arr,equalArea[1]+1,R);

    }

Отличие в том, что добавляется случайный фактор.

Категории