Мало знаний, большой вызов! Эта статья участвует в "Необходимые знания для программистов«Творческая деятельность

Эта статья участвовала в "Проект «Звезда раскопок»”, чтобы выиграть творческий подарочный пакет и бросить вызов творческим поощрительным деньгам.

какОпять же, сделайте это привычкой. Поиск в WeChat【код] Обратите внимание на этого программиста, который борется в Интернете.

Эта статья включена вgithub-Техническая экспертная практика, с моей в немМаршруты обучения, серия статей, банк вопросов для интервью, материалы для самостоятельной работы, электронные книгиЖдать.

---

Привет всем, я ~

Приведение вас сегодняАлгоритм сортировкиобъяснение. Я считаю, что будь то исследование новичка или интервью с крупной фабрикой, алгоритм сортировки незаменим.Даже если вы не выучили алгоритм, даПузырьковая сортировкаИ это не незнакомо.

Сегодня одна часть проведет вас через«Алгоритм сортировки».Это препятствие на уровне няниРекомендуемая коллекция. ⭐️

Эта статья поддерживает адрес исходного кода:Исходный код "Восемь видов", код извлечения: 5ehp

Подготовить

Старая поговорка гласит: «Войска и лошади не двигаются, в первую очередь идут еда и трава». Если вы хотите понять «алгоритм сортировки» один за другим, рекомендуется сначала подготовить следующие шаблоны кода.

📢 Чтобы посмотреть этот урок, вам нужно знать основысинтаксис цикла,Поменять местами два номера,двойной указательи другие предварительные знания.

📚 Рекомендуется сначала прочитатькодипошаговый анализТогда попробуйте написать его сами.

• создать новыйJavaВся статья также основана на языке Java для реализации кода.
• Создайте следующую структуру каталогов

• существуетMainTestНапишите тестовые шаблоны в тестовых классах.

/**
 * 测试类
 * Author：一条
 * Date：2021/09/23
 */
public class MainTest {
    public static void main(String[] args) {
        //待排序序列
        int[] array={6,10,4,5,2,8};
        //调用不同排序算法
				// BubbleSort.sort(array);

        // 创建有100000个随机数据的数组
        int[] costArray=new int[100000];
        for (int i = 0; i < 100000; i++) {
            // 生成一个[0,100000) 的一个数
            costArray[i] = (int) (Math.random() * 100000);
        }

        Date start = new Date();
        //过长，先注释掉逐步打印
				//BubbleSort.sort(costArray);
        Date end = new Date();
        System.out.println("耗时："+(end.getTime()-start.getTime())/1000+"s");
    }
}

Содержание этого кода в основном имеет две функции:

• Вызов различных алгоритмов сортировки для тестирования
• Тестирование различных алгоритмов сортировки10wВремя, необходимое для сортировки чисел. более конкретное пониманиевременная сложностьразница

Пузырьковая сортировка

Основная идея

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

Он постепенно поднимается вверх, как пузыри под водой.

Объяснение анимации


Код

Друзья, которые не понимают, могут использоватьdebugПоэтапный анализ паттернов.

/**
 * 冒泡排序
 * Author：一条
 * Date：2021/09/23
 */
public class BubbleSort{
    public static int[] sort(int[] array){
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array.length-1; j++) {
              //依次比较，将最大的元素交换到最后
                if (array[j]>array[j+1]){
                  // 用临时变量temp交换两个值
                    int temp=array[j];
                    array[j]=array[j+1];
                    array[j+1]=temp;
                }
            }
          //输出每一步的排序结果
            System.out.println(Arrays.toString(array));
        }
        return array;
    }
}

выходной результат

пошаговый анализ

1. Исходный массив:[6,10,4,5,2,8]
2. 6вынуть и последний10сравнивать,6<10, без обмена. ->j++;
3. 10вынуть и последний4сравнивать,10>4,обмен. ->[6,4,10,5,2,8]
4. выполнять последовательноj++с последнимсравнить обмен.
5. первый уровеньiПосле цикла выведите первую строку ->[6, 4, 5, 2, 8, 10], то последний10в правильном положении. ->i++
6. от4начать, продолжитьсравнить обмен, предпоследний8вернуться в правильное положение.
7. Цикл продолжается, как указано выше ->  …
8. конечный результат ->[2, 4, 5, 6, 8, 10]

Затем вернитесь и посмотрите на анимацию, чтобы понять.

длительный тест

Не забудьте сначала закомментировать класс сортировки, чтобы распечатать код шаг за шагом.

временная сложность:O(n^2)

Оптимизация алгоритма

первый пункт оптимизации

После того, как внешний слой пройден в первый раз, последний бит уже правильный,jдальнейшее сравнение не требуется, поэтому конечное условие должно быть изменено наj-i-1;.

Второй пункт оптимизации

Потому что в процессе сортировки каждый элемент постоянно приближается к своей позиции, если после сравнения нет обмена, значит последовательность в порядке, поэтому в процессе сортировки должен быть установлен флаг.flagОпределяет, был ли элемент заменен. Тем самым уменьшая ненужные сравнения.

оптимизировать код

public static int[] sortPlus(int[] array){
        System.out.println("优化冒泡排序开始----------");
        for (int i = 0; i < array.length; i++) {
            boolean flag=false;
            for (int j = 0; j < array.length-i-1; j++) {
                if (array[j]>array[j+1]){
                    flag=true;
                    int temp=array[j];
                    array[j]=array[j+1];
                    array[j+1]=temp;
                }
            }
            if (flag==false){
                break;
            }
//            System.out.println(Arrays.toString(array));
        }
        return array;
    }

оптимизационный тест

Основной тест видит, что цикл прекращается, когда последовательность уже отсортирована, то есть не возникает своп.

Длительный тест27sоптимизирован для17s.

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

Основная идея

Сортировка выбором очень похожа на пузырьковую сортировку: она выбирает элемент из данных в неупорядоченной последовательности в соответствии с заданными правилами, а затем меняет местами позиции в соответствии с правилами для достижения цели сортировки.

Объяснение анимации


Код

public class SelectSort {
    public static int[] sort(int[] array) {
        System.out.println("选择排序开始----------");
        for (int i = 0; i < array.length; i++) {
          //每个值只需与他后面的值进行比较，所以从开始
            for (int j = i; j < array.length; j++) {
              //注意此处是哪两个值比较
                if (array[i]>array[j]){
                    int temp=array[i];
                    array[i]=array[j];
                    array[j]=temp;
                }
            }
            System.out.println(Arrays.toString(array));
        }
        return array;
    }
}

выходной результат

пошаговый анализ

• Исходный массив:[6,10,4,5,2,8]
• выиграть6и10Сравнивать, а не менять местами ->j++
• 6и2сравнить, поменять местами ->j++
• Обратите внимание, что на этот раз2Продолжайте сравнивать, не меняя местами, и определите первый бит (наименьшее число) как2 - > i++
• Продолжайте цикл, найдите первое наименьшее, второе наименьшее и количество...
• конечный результат ->[2, 4, 5, 6, 8, 10]

Затем вернитесь и посмотрите на анимацию, чтобы понять.

длительный тест

временная сложность:O(n^2)

Оптимизация алгоритма

Используемый код апелляцииобменспособ найти меньшее значение, вы также можете использоватьпереехатькстати, то есть только один обмен после всех сравнений.

Такой выигрыш в занимаемом пространстве, но почти никакой выигрыш во времени, можно игнорировать и больше не демонстрировать.

Сортировка вставками

Основная идея

n неупорядоченных элементов рассматриваются как упорядоченный список и неупорядоченный список.В начале упорядоченный список содержит только один элемент, а неупорядоченный список содержит n-1 элементов.Вставьте элементы в таблицу, получите локально правильное решение и постепенно увеличивать длину сортируемой последовательности, пока сортировка не будет завершена.

Объяснение анимации


Код

/**
 * 插入排序
 * Author：一条
 * Date：2021/09/23
 */
public class InsertSort {
    public static void sort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            //插入有序序列，且将有序序列扩大
            for (int j = i; j > 0; j--) {
                if (array[j]>array[j-1]){
                    int temp=array[j];
                    array[j]=array[j-1];
                    array[j-1]=temp;
                }
            }
//            System.out.println(Arrays.toString(array));
        }
    }
}

выходной результат

длительный тест

Оптимизация алгоритма

увидеть нижеСортировка холмов, то есть Хилл справаСортировка вставкамиОптимизация.

Сортировка холмов

Сортировка по Хиллу — это оптимизация сортировки вставками с учетом[2,3,4,5,6]вставлять1, положение всех элементов нужно переместить один раз, то есть в некоторых крайних случаях это неэффективно, также известный как алгоритмнестабильный.

Сортировка по Хиллу — это улучшенная и более эффективная версия сортировки вставками, также известной какУзкая сортировка по возрастанию.

Основная идея

Сортировка по Хиллу предназначена для группировки записей по определенному приращению нижнего индекса и использования сортировки вставками для каждой группы;

По мере постепенного уменьшения приращения каждая группа содержит все больше и больше ключевых слов, при уменьшении приращения до 1 вся последовательность просто делится на одну группу, и алгоритм останавливается.

Подобно сортировке вставками, от частичного к общему, сортировка Хилла является частичной к частичной.

Объяснение анимации

Код

/**
 * 希尔排序
 * Author：一条
 * Date：2021/09/23
 */
public class ShellSort {
    public static void sort(int[] array) {
        System.out.println("希尔排序开始--------");
        //gap初始增量=length/2  逐渐缩小：gap/2
        for (int gap = array.length/2; gap > 0 ; gap/=2) {
            //插入排序 交换法
            for (int i = gap; i < array.length ; i++) {
                int j = i;
                while(j-gap>=0 && array[j]<array[j-gap]){
                    //插入排序采用交换法
                    int temp = array[j];
                    array[j]=array[j-gap];
                    array[j-gap]=temp;
                    j-=gap;
                }
            }
            System.out.println(Arrays.toString(array));
        }
    }
}

выходной результат

длительный тест

Оптимизация алгоритма

никто

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

Быстрая сортировка — это усовершенствование пузырьковой сортировки.По сравнению с пузырьковой сортировкой каждый обмен пропускается.

Основная идея

Разделите данные для сортировки на две независимые части, и все данные в одной части меньше, чем все данные в другой части, а затем быстро отсортируйте две части данных в соответствии с этим методом Весь процесс сортировки может быть рекурсивно выполнено Это позволяет привести все данные в упорядоченную последовательность.

Отражатьразделяй и властвуйподумал о.

Объяснение анимации


Код

Идея заключается в следующем:

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

public class QuickSort {
    public static void sort(int[] array) {
        System.out.println("快速排序开始---------");
        mainSort(array, 0, array.length - 1);
    }

    private static void mainSort(int[] array, int left, int right) {
        if(left > right) {
            return;
        }
        //双指针
        int i=left;
        int j=right;
        //base就是基准数
        int base = array[left];
        //左边小于基准，右边大于基准
        while (i<j) {
            //先看右边，依次往左递减
            while (base<=array[j]&&i<j) {
                j--;
            }
            //再看左边，依次往右递增
            while (base>=array[i]&&i<j) {
                i++;
            }
            //交换
            int temp = array[j];
            array[j] = array[i];
            array[i] = temp;
        }
        //最后将基准为与i和j相等位置的数字交换
        array[left] = array[i];
        array[i] = base;
        System.out.println(Arrays.toString(array));
        //递归调用左半数组
        mainSort(array, left, j-1);
        //递归调用右半数组
        mainSort(array, j+1, right);
    }
}

выходной результат

пошаговый анализ

• будет6В качестве ссылочного номера используйте левый и правый указатели, чтобы число слева<6, номер справа>6.
• Рекурсия по левой и правой сторонам, то есть левая сторона использует5Продолжите сравнение в качестве эталона.
• до того какleft > rightЗавершить рекурсию.

длительный тест

Почему быстрая сортировка такая быстрая?

Оптимизация алгоритма

оптимизировать один

Медиана трех: в настоящее время мы используем первое число в качестве эталонного числа. Для некоторых упорядоченных последовательностей цикл будет потрачен впустую. Вы можете использовать метод трех чисел для оптимизации. Перцептивные друзья могут понять сами.

Оптимизация вторая

Быстрая сортировка работает очень быстро для длинных последовательностей, но не так быстро, как сортировка вставками для коротких последовательностей. Можно использовать в комбинации.

сортировка кучей

Эта глава требует более базовых знаний и может быть пропущена новичками.

Основная идея

Используется кучевая сортировкакучаАлгоритм сортировки, разработанный для этой структуры данных, сортировка кучей является **сортировкой выбором**, ее худшая, лучшая, средняя временная сложность равнаO(nlogn), который также является нестабильным сортом. Во-первых, краткое понимание структуры кучи.

куча

Куча — это полное бинарное дерево со следующими свойствами:

• Значение каждого узла больше или равно значению его левого и правого дочерних узлов, которые называются большой верхней кучей;
• Значение каждого узла меньше или равно значению его левого и правого дочерних узлов, что называется малой верхней кучей.

В основном используйте максимальные или минимальные характеристики верхнего элемента кучи, непрерывно строябольшая куча, поменять местами вершину кучи и хвост кучи и реализовать сортировку путем реконструкции с разрывом хвоста.

Объяснение анимации

Код

public class HeapSort {
    public static void sort(int[] array) {
        //创建堆
        for (int i = (array.length - 1) / 2; i >= 0; i--) {
            //从第一个非叶子结点从下至上，从右至左调整结构
            adjustHeap(array, i, array.length);
        }

        //调整堆结构+交换堆顶元素与末尾元素
        for (int i = array.length - 1; i > 0; i--) {
            //将堆顶元素与末尾元素进行交换
            int temp = array[i];
            array[i] = array[0];
            array[0] = temp;

            //重新对堆进行调整
            adjustHeap(array, 0, i);
        }
    }

    /**
     * 调整堆
     * @param array 待排序列
     * @param parent 父节点
     * @param length 待排序列尾元素索引
     */
    private static void adjustHeap(int[] array, int parent, int length) {
        //将temp作为父节点
        int temp = array[parent];
        //左孩子
        int lChild = 2 * parent + 1;
        while (lChild < length) {
            //右孩子
            int rChild = lChild + 1;
            // 如果有右孩子结点，并且右孩子结点的值大于左孩子结点，则选取右孩子结点
            if (rChild < length && array[lChild] < array[rChild]) {
                lChild++;
            }
            // 如果父结点的值已经大于孩子结点的值，则直接结束
            if (temp >= array[lChild]) {
                break;
            }
            // 把孩子结点的值赋给父结点
            array[parent] = array[lChild];
            //选取孩子结点的左孩子结点,继续向下筛选
            parent = lChild;
            lChild = 2 * lChild + 1;
        }
        array[parent] = temp;
        System.out.println(Arrays.toString(array));
    }
}

выходной результат

пошаговый анализ

1. Создайте начальную кучу, сформируйте большую верхнюю кучу (или маленькую верхнюю кучу) столбцов для сортировки, восходящую большую верхнюю кучу и нисходящую малую верхнюю кучу;
2. Поменяйте местами верхний элемент с хвостовым элементом и отсоедините (удалите из столбца для сортировки) хвостовой элемент.
3. Восстановите кучу.
4. Повторяйте 2–3, пока в столбце для сортировки не останется только один элемент (верхний элемент кучи).

длительный тест

Оптимизация алгоритма

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

Сортировка слиянием

Основная идея

Сортировка слиянием (MERGE-SORT) заключается в использованиисливатьсяИдея реализации метода сортировки с использованием классическогоразделяй и властвуй(разделяй и властвуй) стратегия.

Неупорядоченная последовательность постоянно делится на две части, сортируется, затем записывается обратно и реализуется рекурсивно.

Трудность заключается вКак объединить два отсортированных массива?

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

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

Поэтому обмен пространства на время также является направлением при оптимизации алгоритма.

Объяснение анимации


Код

public class MergeSort {
    public static void sort(int[] array){
        divide(array,0,array.length-1);
    }

    private static int[] divide(int[] array, int left, int right) {
        int mid = (left+right)/2;
        if(left<right){
            divide(array,left,mid);
            divide(array,mid+1,right);
            //左右归并
            merge(array,left,mid,right);
        }
        System.out.println(Arrays.toString(array));
        return array;
    }

    public static void merge(int[] array, 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(array[i]<array[j]){
                temp[k++] = array[i++];
            }else{
                temp[k++] = array[j++];
            }
        }
        // 把左边剩余的数移入数组
        while(i<=mid){
            temp[k++] = array[i++];
        }
        // 把右边边剩余的数移入数组
        while(j<=right){
            temp[k++] = array[j++];
        }
        // 把新数组中的数覆盖nums数组
        for(int x=0;x<temp.length;x++){
            array[x+left] = temp[x];
        }
    }
}

выходной результат

длительный тест

Оптимизация алгоритма

сортировка по подсчету

Это все отсюданесравнительная сортировка.

Основная идея

Если вы введете числоx, если мы сможем найти, сколько чисел меньше этого числа, то мы можем напрямую преобразоватьxв соответствующую позицию выходного массива. Например, в тестовой последовательностиx=5,Сравнивать5маленький2один, тогда не сомневайтесь5Должен быть на третьем месте.

Объяснение анимации


Код

public class CountSort {
    public static void sort(int[] array) {
        System.out.println("计数排序开始--------");
        //计算最大值和最小值，用于确定count[]的长度
        int max = array[0], min = array[0];
        for (int i : array) {
            if (i > max) {
                max = i;
            }
            if (i < min) {
                min = i;
            }
        }
        //count[]用于存储每个元素出现的次数
        int[] count = new int[max - min + 1];

        //统计出现的频次
        for (int i : array) {
            count[i - min] += 1;//数的位置 上+1
        }

        //创建最终返回的数组，和原始数组长度相等，但是排序完成的
        int[] result = new int[array.length];
        int index = 0;//记录最终数组的下标

        //先循环每一个元素  在计数排序器的下标中
        for (int i = 0; i < count.length; i++) {
            //遍历循环出现的次数
            for (int j = 0; j < count[i]; j++) {//count[i]:这个数出现的频率
                result[index++] = i + min;//以为原来减少了min现在加上min，值就变成了原来的值
            }
            System.out.println(Arrays.toString(result));
        }
    }
}

выходной результат

пошаговый анализ

• Он заключается в записи частоты (количества раз) значений исходного массива в индекс нового массива.
• Перебрать количество вхождений и по очереди поместить их в новый массив.

длительный тест

Честно говоря, скорость меня удивила.сортировка по подсчетуВременная сложностьO(n), недостатком является то, что диапазон предельных значений[0,k]целое число.

Оптимизация алгоритма

Обычная сортировка от0В начале код, реализованный в этой статье, начинается сminСтарт, оптимизация.

Суммировать

Эта статья специально не вводит временную сложность, потому что я поставил здесь число, и вы не можете понять разницу между ними.

использовать100000Массивы длины проверяют восемь алгоритмов сортировки, превращая абстракции в конкретные. Когда объем данных большойnlognпреимущество будет по сравнению сn^2становится все больше и больше, когдаn=10^5когда,nlognалгоритм, чемn^2алгоритм быстрый6000Времена, что за концепция, то есть если мы хотим обработать набор данных, используемnlognЕсли алгоритм должен обрабатывать один день, используйтеn^2Алгоритм будет обрабатывать6020небо. Это в основном эквивалентно15год.

Оптимизированный и улучшенный алгоритм может быть намного быстрее, чем глупый алгоритм, поэтому большая фабрика проверяет алгоритм, а мы изучаем алгоритм.

Старая поговорка гласит:Если вы используете мудрость толпы, вы будете непобедимы, если вы используете силу толпы, вы будете непобедимы.Для того, чтобы преодолеть гору алгоритмов, я сформулировалЧистка командыплан, по крайней мере, каждый день1 вопрос по алгоритму leetcode.

Десять лошадей гонят, а работу бросать не хочется.

если ты простопервокурсник, продолжайте учиться каждый день, выКак минимумЧистите больше, чем другие1200 вопросов, то ваша зарплата может быть чужой, когда вы закончите3-4 раза.

Что, если выПрофессиональный, Совершенствуйтесь каждый день, получайте повышение и повышение зарплаты, становитесь техническим экспертомПрямо за углом.

Пока вы готовы бороться и всегда идти по дороге тяжелой работы, тогда ваша жизнь, худший результат, будет просто поздним расцветом.

кликните сюдаПрисоединяйтесь к программе

Если ссылка заблокирована или есть проблема с разрешением, вы можете лично пообщаться с автором, чтобы решить эту проблему.