Быстрая сортировка — это улучшение пузырьковой сортировки, основанное на двоичной идее. Основная идея состоит в том, чтобы установить основание, поместить числа, меньшие, чем основание, слева от основания, а числа, большие, чем основание, справа от основания, а затем дополнительно отсортировать две части чисел для достижения сортировка массива.
Его преимуществом является высокая эффективность, а средняя временная сложность равна O(nlogn). Как следует из названия, быстрая сортировка является самым быстрым алгоритмом сортировки и потребляет мало ресурсов. В лучшем случае пространственная сложность равна O(logn). каждый раз делится поровну. В случае массивов код относительно прост.
Его недостатком является нестабильность. Когда исходная последовательность упорядочена или в основном упорядочена, временная сложность падает до O(n^2).
Например:
publicclassMain{//Метод реализации быстрой строки publicstaticvoidquickRow(int[]array,intlow,inthigh){inti,j,pivot;//Конечное условие if(low>=high){return;}i=low;j=high;/ /Выбранный узел, первый номер выбранного здесь массива используется в качестве узла Pivot=array[low ]; while(i<j){//Поиск числа, меньшего, чем узел, справа налево. В конце цикла либо оно найдено, либо i=j while(array[j]>=pivot&&i<j. ){j--;}/ /Ищем раздел слева направо Укажите на большее число. В конце цикла либо оно найдено, либо i=j while(array[i]<=pivot&&i<j){i++;}//Если i!=j означает, что оба найдены, поменяйте местами. два числа if( i<j){i nttemp=array[i];array[i]=array[j];array[j]=temp;}}//i==jВ конце цикла поменяйте местами количество узлов и количество точек встречи массива [low] =array[i];array[i]=pivot;//Массив «делится на две половины», а затем повторяем описанную выше операцию fastRow(array,low,i-1);quickRow(array,i +1,high);}publicstaticvoidmain(String[]args){int[]array={6,17,38,59,2,10};intlow=0,high=array.length-1;quickRow(array, низкий, высокий); for (inti: array) {System.out.println (i);}}}Результаты бега следующие:
2610173859