предисловие
На сортировку восьми основ ушло около недели.Этот пост в блоге в основном используется для обзора основных моментов восьми основ и некоторых резюме~
обзор:
- Пузырьковая сортировка так же проста
- Сортировка выбором так проста
- Сортировка вставками так же проста
- Быстрая сортировка так же проста
- Сортировка слиянием так проста
- Сортировка кучей так проста
- Сортировка по холму так же проста
- Сортировка по основанию так же проста, как это
В целом:Быстрая сортировка является широко используемой сортировкой, а также часто встречающейся сортировкой, которую следует осваивать с особым вниманием~
2. Резюме восьми основных рейтингов
2.1 Пузырьковая сортировка
Идеи:
- Две меняем местами, а большую ставим сзади.После первой сортировки максимальное значение уже в конце массива.
- Поскольку два обмена, нужно
n-1Сортировка, например 10 номеров, требует 9 сортировки
Точки реализации кода:
-
Два цикла for, внешний цикл контролирует количество раз сортировки, а внутренний цикл контролирует количество сравнений.
- После каждого прохода количество сравнений должно уменьшаться на 1.
- Оптимизация: Если после сортировки позиции обмена нет, то массив сортируется~
//外层循环是排序的趟数
for (int i = 0; i < arrays.length -1 ; i++) {
//每比较一趟就重新初始化为0
isChange = 0;
//内层循环是当前趟数需要比较的次数
for (int j = 0; j < arrays.length - i - 1; j++) {
//前一位与后一位与前一位比较，如果前一位比后一位要大，那么交换
if (arrays[j] > arrays[j + 1]) {
temp = arrays[j];
arrays[j] = arrays[j + 1];
arrays[j + 1] = temp;
//如果进到这里面了，说明发生置换了
isChange = 1;
}
}
//如果比较完一趟没有发生置换，那么说明已经排好序了，不需要再执行下去了
if (isChange == 0) {
break;
}
}
System.out.println("公众号Java3y" + arrays);
2.2 Сортировка выбором
Идеи:
- Найдите самый большой элемент в массиве и замените его последним элементом массива
- Когда есть только один номер, нет необходимости выбирать, поэтому необходимо
n-1Сортировка, например 10 номеров, требует 9 сортировки
Точки реализации кода:
- Два цикла for, внешний цикл контролирует количество раз сортировки, а внутренний цикл находит максимальное количество текущих проходов, а затем обменивает его с последним элементом массива текущих проходов
//外层循环控制需要排序的趟数
for (int i = 0; i < arrays.length - 1; i++) {
//新的趟数、将角标重新赋值为0
pos = 0;
//内层循环控制遍历数组的个数并得到最大数的角标
for (int j = 0; j < arrays.length - i; j++) {
if (arrays[j] > arrays[pos]) {
pos = j;
}
}
//交换
temp = arrays[pos];
arrays[pos] = arrays[arrays.length - 1 - i];
arrays[arrays.length - 1 - i] = temp;
}
System.out.println("公众号Java3y" + arrays);
2.3 Сортировка вставками
Идеи:
- Вставляя элемент в упорядоченный массив, вначале неизвестно, есть ли упорядоченные данные, поэтому элементПервый элемент считается упорядоченным
- Сравните с упорядоченным массивом,Если он больше, поместите его прямо, если он меньше, переместите позицию элемента массива, чтобы найти подходящую позицию для вставки.
- Когда есть только одно число, вставлять его не нужно, поэтому необходимо
n-1Сортировка, например 10 номеров, требует 9 сортировки
Код:
- Цикл for реализуется со встроенным в него циклом while.Внешний цикл for контролирует количество сортировок.Цикл while находит подходящую позицию вставки (и позиция вставки не может быть меньше 0)
//临时变量
int temp;
//外层循环控制需要排序的趟数(从1开始因为将第0位看成了有序数据)
for (int i = 1; i < arrays.length; i++) {
temp = arrays[i];
//如果前一位(已排序的数据)比当前数据要大，那么就进入循环比较[参考第二趟排序]
int j = i - 1;
while (j >= 0 && arrays[j] > temp) {
//往后退一个位置，让当前数据与之前前位进行比较
arrays[j + 1] = arrays[j];
//不断往前，直到退出循环
j--;
}
//退出了循环说明找到了合适的位置了，将当前数据插入合适的位置中
arrays[j + 1] = temp;
}
System.out.println("公众号Java3y" + arrays);
2.4 Быстрая сортировка
Идеи:
- Найдите элемент (узел) в массиве, поместите меньший элемент слева от узла, а больший элемент поместите справа от узла. Одна поездка вниз, меньше, чем узел слева, и больше, чем узел справа.
- продолжай делать это....
Код:
- Быструю сортировку легче написать с помощью рекурсии [если вы не знакомы с рекурсией, вы можете перейти к:Рекурсия такая простая]. Опорная точка берется посередине, а L и R используются для обозначения минимальной и максимальной позиций массива.
- Продолжайте сравнивать, пока не найдете число меньшее (большее), чем точка опоры, затем поменяйте местами и постоянно уменьшайте диапазон~
- Рекурсия L к предыдущему элементу (j) опорной точки (сделайте то же самое, что и выше)
- Рекурсивный поворот одного элемента (i) к элементу R (сделайте то же самое, что и выше)
/**
* 快速排序
*
* @param arr
* @param L 指向数组第一个元素
* @param R 指向数组最后一个元素
*/
public static void quickSort(int[] arr, int L, int R) {
int i = L;
int j = R;
//支点
int pivot = arr[(L + R) / 2];
//左右两端进行扫描，只要两端还没有交替，就一直扫描
while (i <= j) {
//寻找直到比支点大的数
while (pivot > arr[i])
i++;
//寻找直到比支点小的数
while (pivot < arr[j])
j--;
//此时已经分别找到了比支点小的数(右边)、比支点大的数(左边)，它们进行交换
if (i <= j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
//上面一个while保证了第一趟排序支点的左边比支点小，支点的右边比支点大了。
//“左边”再做排序，直到左边剩下一个数(递归出口)
if (L < j)
quickSort(arr, L, j);
//“右边”再做排序，直到右边剩下一个数(递归出口)
if (i < R)
quickSort(arr, i, R);
}
2.5 Сортировка слиянием
Идеи:
- Объединяет два отсортированных массива в один отсортированный массив.
- Разделите элементы как упорядоченный массив, сравните и объедините
- Держите расщепление и слияние, пока не будет только один элемент
Код:
- В первой сортировке суть в том, чтобы объединить два элемента (как два отсортированных массива), и далее выполнять такие операции, и, наконец, массив сортируется.
- Разделить налево, направо, объединить...
public static void main(String[] args) {
int[] arrays = {9, 2, 5, 1, 3, 2, 9, 5, 2, 1, 8};
mergeSort(arrays, 0, arrays.length - 1);
System.out.println("公众号：Java3y" + arrays);
}
/**
* 归并排序
*
* @param arrays
* @param L 指向数组第一个元素
* @param R 指向数组最后一个元素
*/
public static void mergeSort(int[] arrays, int L, int R) {
//如果只有一个元素，那就不用排序了
if (L == R) {
return;
} else {
//取中间的数，进行拆分
int M = (L + R) / 2;
//左边的数不断进行拆分
mergeSort(arrays, L, M);
//右边的数不断进行拆分
mergeSort(arrays, M + 1, R);
//合并
merge(arrays, L, M + 1, R);
}
}
/**
* 合并数组
*
* @param arrays
* @param L 指向数组第一个元素
* @param M 指向数组分隔的元素
* @param R 指向数组最后的元素
*/
public static void merge(int[] arrays, int L, int M, int R) {
//左边的数组的大小
int[] leftArray = new int[M - L];
//右边的数组大小
int[] rightArray = new int[R - M + 1];
//往这两个数组填充数据
for (int i = L; i < M; i++) {
leftArray[i - L] = arrays[i];
}
for (int i = M; i <= R; i++) {
rightArray[i - M] = arrays[i];
}
int i = 0, j = 0;
// arrays数组的第一个元素
int k = L;
//比较这两个数组的值，哪个小，就往数组上放
while (i < leftArray.length && j < rightArray.length) {
//谁比较小，谁将元素放入大数组中,移动指针，继续比较下一个
if (leftArray[i] < rightArray[j]) {
arrays[k] = leftArray[i];
i++;
k++;
} else {
arrays[k] = rightArray[j];
j++;
k++;
}
}
//如果左边的数组还没比较完，右边的数都已经完了，那么将左边的数抄到大数组中(剩下的都是大数字)
while (i < leftArray.length) {
arrays[k] = leftArray[i];
i++;
k++;
}
//如果右边的数组还没比较完，左边的数都已经完了，那么将右边的数抄到大数组中(剩下的都是大数字)
while (j < rightArray.length) {
arrays[k] = rightArray[j];
k++;
j++;
}
}
2.6 Сортировка кучей
Идеи:
- Сортировка кучей использует функцию полного бинарного дерева [Студенты, которые не понимают бинарные деревья, могут перейти к:Бинарное дерево так простоВолна обучения], корневой узел больше, чем левый дочерний и правый дочерние элементы, полныйПостроить кучуПо сути, операция заключается в сравнении размера корневого узла, левого и правого дочерних узлов и замене большего на корневой узел.пока самый большой узел не окажется на вершине дерева
- Затем поменяйте местами последний элемент массива
- ......
Код:
- Заменять всякий раз, когда левое поддерево или правое поддерево больше, чем текущий корневой узел. После замены изменятся следующие поддеревья, поэтому сравнивать также необходимо до тех пор, пока каждый узел не достигнет состояния родитель>потомок
public static void main(String[] args) {
int[] arrays = {6, 3, 8, 7, 5, 1, 2, 23, 4321, 432, 3,2,34234,2134,1234,5,132423, 234, 4, 2, 4, 1, 5, 2, 5};
for (int i = 0; i < arrays.length; i++) {
//每完成一次建堆就可以排除一个元素了
maxHeapify(arrays, arrays.length - i);
//交换
int temp = arrays[0];
arrays[0] = arrays[(arrays.length - 1) - i];
arrays[(arrays.length - 1) - i] = temp;
}
System.out.println("公众号：Java3y" + arrays);
}
/**
* 完成一次建堆，最大值在堆的顶部(根节点)
*/
public static void maxHeapify(int[] arrays, int size) {
for (int i = size - 1; i >= 0; i--) {
heapify(arrays, i, size);
}
}
/**
* 建堆
*
* @param arrays 看作是完全二叉树
* @param currentRootNode 当前父节点位置
* @param size 节点总数
*/
public static void heapify(int[] arrays, int currentRootNode, int size) {
if (currentRootNode < size) {
//左子树和右字数的位置
int left = 2 * currentRootNode + 1;
int right = 2 * currentRootNode + 2;
//把当前父节点位置看成是最大的
int max = currentRootNode;
if (left < size) {
//如果比当前根元素要大，记录它的位置
if (arrays[max] < arrays[left]) {
max = left;
}
}
if (right < size) {
//如果比当前根元素要大，记录它的位置
if (arrays[max] < arrays[right]) {
max = right;
}
}
//如果最大的不是根元素位置，那么就交换
if (max != currentRootNode) {
int temp = arrays[max];
arrays[max] = arrays[currentRootNode];
arrays[currentRootNode] = temp;
//继续比较，直到完成一次建堆
heapify(arrays, max, size);
}
}
}
2.7 Сортировка по холму
Идеи:
- Сортировка по холму, по сути, является расширенной версией сортировки вставками. Сортировка по холму делит массив на n групп для сортировки вставками, **пока массив не будет макроскопически упорядочен, **в конце вам не нужно перемещаться так много раз при выполнении сортировка вставками расположение~
Идея кода:
- Приращение Хилла обычно
gap = gap / 2, всего на один цикл for больше, чем в обычной версии сортировки вставками, это не так уж сложно
/**
* 希尔排序
*
* @param arrays
*/
public static void shellSort(int[] arrays) {
//增量每次都/2
for (int step = arrays.length / 2; step > 0; step /= 2) {
//从增量那组开始进行插入排序，直至完毕
for (int i = step; i < arrays.length; i++) {
int j = i;
int temp = arrays[j];
// j - step 就是代表与它同组隔壁的元素
while (j - step >= 0 && arrays[j - step] > temp) {
arrays[j] = arrays[j - step];
j = j - step;
}
arrays[j] = temp;
}
}
}
2.8 Сортировка по основанию
Идеи:
- Сортировка по кардинальности (сортировка ведрами): разделите числа на единицы, десятки, сотни и тысячи и поместите их в разные ведра.После размещения они будут перерабатываться в порядке ведер, пока не будет найдено число с наибольшим количеством цифр. Готово. Тогда массив в порядке
Код:
- Сначала найдите максимальное значение массива, а затем используйте максимальное значение/10 в качестве условия цикла (пока оно> 0, это означает, что цифры все еще есть)
- Выделите единицы, десятки, ... в ведро и перерабатывайте его каждый раз, когда он выделяется
public static void main(String[] args) {
int[] arrays = {6, 4322, 432, 344, 55, 234, 45, 243, 5, 2, 4, 5, 6, 7, 3245, 345, 345, 234, 68, 65};
radixSort(arrays);
System.out.println("公众号：Java3y" + arrays);
}
public static void radixSort(int[] arrays) {
int max = findMax(arrays, 0, arrays.length - 1);
//需要遍历的次数由数组最大值的位数来决定
for (int i = 1; max / i > 0; i = i * 10) {
int[][] buckets = new int[arrays.length][10];
//获取每一位数字(个、十、百、千位...分配到桶子里)
for (int j = 0; j < arrays.length; j++) {
int num = (arrays[j] / i) % 10;
//将其放入桶子里
buckets[j][num] = arrays[j];
}
//回收桶子里的元素
int k = 0;
//有10个桶子
for (int j = 0; j < 10; j++) {
//对每个桶子里的元素进行回收
for (int l = 0; l < arrays.length ; l++) {
//如果桶子里面有元素就回收(数据初始化会为0)
if (buckets[l][j] != 0) {
arrays[k++] = buckets[l][j];
}
}
}
}
}
/**
* 递归，找出数组最大的值
*
* @param arrays 数组
* @param L 左边界，第一个数
* @param R 右边界，数组的长度
* @return
*/
public static int findMax(int[] arrays, int L, int R) {
//如果该数组只有一个数，那么最大的就是该数组第一个值了
if (L == R) {
return arrays[L];
} else {
int a = arrays[L];
int b = findMax(arrays, L + 1, R);//找出整体的最大值
if (a > b) {
return a;
} else {
return b;
}
}
}
3. Резюме
На временную сложность и стабильность сортировки в инете тоже много картинок, так что нашел только одну (вторжение и удаление)
Если учащиеся не понимают определенный порядокЛучше всего найти это в одной статье, которую я написал, потому что есть шаги, чтобы разбить ее.~
Я также загрузил код (включая процесс декомпозиции) на GitHub, и я поместил в него код алгоритма и структуры данных. Добро пожаловать в звезду~ Я также позже напишу сообщения в блоге, связанные со стеками и очередями, так что следите за обновлениями.. .
- Адрес гитхаба:GitHub.com/Zhongf UC очень…
Свободное время:
- Каковы самые передовые знания алгоритмов, которые вы использовали в своей жизни? , ответьте много про сортировку, очень интересноУуху. Call.com/question/67…
Использованная литература:
- блог woo woo woo.cn на.com/happy плотно/afraid/55…
- Блог Woohoo.cn на.com/sky.net 1234…
- blog.ChinaUnix.net/UID-2145720…
Если в статье есть какие-либо ошибки, пожалуйста, поправьте меня, и мы сможем общаться друг с другом. Учащиеся, привыкшие читать технические статьи в WeChat и желающие получить больше ресурсов по Java, могутОбратите внимание на публичный аккаунт WeChat: Java3y