Быстрая сортировка заставила меня долго на это смотреть и долго мучила, потому что общее представление у меня есть, но при написании кода всегда возникают различные проблемы. Лично мне пока сложно его отлаживать. определенная степень сложности, а из-за работы и лени ошибки, которые не удалось отладить, были давно убраны. Сегодня он наконец-то вышел, и я все еще немного взволнован. Позвольте мне поделиться своим кодом и дать. небольшое объяснение.
Чтобы научиться быстрой сортировке, вы должны сначала изучить метод «разделяй и властвуй». Идея метода «разделяй и властвуй» состоит в том, чтобы дать строку неупорядоченных чисел (числа являются предположениями, они также могут быть другими объектами. Конечно, параметры метода можно определить самому. Я вот предположим, есть массив целых чисел) и потом передать его ему. Среднее число, метод «разделяй и властвуй» разделит эти числа на две части на основе присвоенного ему среднего числа: одна часть находится слева от среднего числа, а другая часть — справа, используя это число в качестве среднего. точка разделения, числа с обеих сторон все еще не в порядке, я определил это следующим образом:
//слева — это левая конечная точка разделяющей и властвующей части массива, а справа — общая конечная точка разделяющей и властвующей части массива. Например, для массива длиной 10, если. Я хочу разделить и победить первые 5 целых чисел, я могу передать 0 или 4 как public int signalFenZhi(int left,int right){ if(left<0||left>n-1||right<0||right> n-1) {возвращение -1} int temp = test [left]; j=right; int i=left; while(i<j){ while(test[j]>=test[left]&&i<j){ j--; } while(test[i]<=test[left] &&i<j){ i++; } if(i<j){ temp = test[i]; test[i]=test[j]; test[j]=temp; } } if(i==j){ temp = тест [я]; test[i]=test[left]; test[left]=temp; } for(int m=0;m<n;m++){ System.out.print(test[m]+" "); ; }Конечно, вы также можете передать среднее число в качестве параметра. Теперь я просто использую переданное левое число в качестве разделительного числа. Это просто для иллюстрации.
После понимания «разделяй и властвуй» быстрая сортировка становится простой. То есть разделяй и властвуй числа, которые были разделены на две части, и так далее, пока все числа не будут в порядке.
public void QuickSort(int left,int right){ if(right-left<1){ return }else { int point = this.signalFenZhi(left, right); System.out.println(point); point!=left&&point!=right){ fastSort(left,point-1);Эффективность быстрой сортировки превосходна среди многих алгоритмов сортировки. Временная сложность равна O(N*log2n). Однако, если точка разделения выбрана неправильно, временная сложность будет уменьшена до (n в квадрате). ), потому что если этот массив будет отсортирован, а затем мы будем каждый раз брать самое левое переданное число, эффективность будет очень низкой, поэтому мы должны избегать этой ситуации. Если все варианты протестированы, то это займет много времени. время, так что Компромиссный метод состоит в том, чтобы добавить среднее число к самому левому и самому правому числам и найти среди них среднее число. Использование этого значения в качестве значения деления улучшит ситуацию. На основе приведенного выше метода модифицированный код выглядит следующим образом: но после того, как я закончил, этот подход оказался не очень хорош. Было бы лучше передать значение деления как метод «разделяй и властвуй». Осторожные друзья могут попробовать это сами, но я не буду пробовать это здесь, в принципе то же самое!
пакет com.jll; общественный класс FenZhi { int [] test; int n = 10; public FenZhi () {test = new int [10]; =(int)(Math.random()*100)+1; System.out.print(test[i]+" "); } System.out.println(); n) { if(n>0){ this.n=n; test = new int[n]; for(int i=0;i<n;i++){test[i]=(int)(Math.random ()*100)+1; } } } public int signalFenZhiMajorizationFirst(int left,int right){ if(left<0||left>n-1||right<0||right>n-1||left>=right){ return -1 } if(right-left>=2){ int middle = (вправо+влево)/2; if(test[left]>test[middle]){ int temp = test[middle]; test[left]; test[left] = temp; if(test[left]>test[right]){ int temp = test[left]; test[left] = test[right]; test[right] = temp; } if(test[middle]>test[right] ) { int temp = test[middle] = test[right]; test[right] = temp; } int temp = test[middle]; test[left]; = temp; int j=right-1; int i=left+1; while(i<j){ while(test[j]>=test[left]&&i<j){ j--; ]<=test[left]&&i<j){ i++; } if(i<j){ temp = test[i]; test[i]=test[j]; test[j]=temp; я==j){ temp = test[i]; test[i]=test[left]; test[left]=temp; } /*if(i==j){ temp = test[middle]; ]; test[i]=temp; }*/ /*for(int m=0;m<n;m++){ System.out.print(test[m]+" "); еще { if(test[right]<test[left]){ int temp = test[right]; test[right] = test[left] = temp; } } public void QuickSortMajorizationFirst(int left) ,int right){ if(right-left<1){ return ; }else{ int point = this.signalFenZhiMajorizationFirst(left, right); System.out.println("точка" это: "+point); QuickSortMajorizationFirst(left,point-1); QuickSortMajorizationFirst(point+1,right); } } public static void main(String[] args) { FenZhi f = new FenZhi(); System.out. println(f.signalFenZhiMajorizationFirst(0, 9)); System.out.println(); f.quickSortMajorizationFirst(0,fn-1); //f.quickSort(0,f.test.length-1); for(int i:f.test){ System.out.print(i+" "); }}Код работает следующим образом:
95 40 64 18 78 23 73 84 40 точка: 4 точка: 1 точка: 3 точка: 7 точка: 6 точка: 918 23 40 40 64 73 78 84 95
Вышеизложенное — это то, что я узнал, запишите это для дальнейшего использования.