сортировка выбором
Принцип реализации
Сначала найдите наименьший элемент в несортированной последовательности и поместите его в начало отсортированной последовательности, затем продолжайте находить наименьший элемент из оставшейся несортированной последовательности и поместите его в конец отсортированной последовательности. Поэтому это называется сортировкой выбором.
Код
public static int[] selectionSort(int[] arr){
if (null == arr || arr.length == 0){
return null;
}
int length = arr.length;
for (int i = 0; i < length - 1; i++) {
int min = i;
for (int j = i + 1; j < length; j++) {
if (arr[j] < arr[min]){
min = j;
}
}
int temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
return arr;
}
анализ случая
временная сложность и пространственная сложность
Минимальное значение находится каждый раз, а в худшем случае — n раз.Этот процесс необходимо выполнить n раз, поэтому временная сложность по-прежнему O(n^2). Сложность пространства O (1).
быстрая сортировка
Принцип реализации
-
В наборе данных выберите элемент, который будет «осевым».
-
Все элементы меньше «базы» перемещаются влево от «базы», все элементы больше «базы» перемещаются вправо от «базы». Эта операция называется разделом.
После завершения операции разбиения положение базового элемента является его положением после окончательной сортировки.
-
Чтобы «ориентировать» два подмножества левых и справа, повторите шаги по одному и два, пока все подмножества пока не так далеко не только один элемент.
Код
public static int partition(int[] array, int lo, int hi) {
// 固定的切分方式
int key = array[lo];
while (lo < hi) {
while (array[hi] >= key && hi > lo) {// 从后半部分向前扫描
hi--;
}
array[lo] = array[hi];
while (array[lo] <= key && hi > lo) {// 从前半部分向后扫描
lo++;
}
array[hi] = array[lo];
}
array[hi] = key;
return hi;
}
public static int[] sort(int[] array, int lo, int hi) {
if (lo >= hi) {
return array;
}
int index = partition(array, lo, hi);
sort(array, lo, index - 1);
sort(array, index + 1, hi);
return array;
}
анализ случая
временная сложность и пространственная сложность
Быстрая сортировка также является нестабильной сортировкой со средней временной сложностью O(nlogn). Пространственная сложность равна O(logn).
Пузырьковая сортировка
Принцип реализации
Сравнивает два соседних элемента по очереди, меняя их позиции, если первый элемент больше второго. После одного раунда сравнения самый большой элемент будет доставлен в конец очереди. Затем этот процесс повторяется для несортированной последовательности, в конечном итоге преобразуясь в упорядоченную последовательность.
Код
public static int[] bubbleSort(int[] arr){
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - i -1; j++) {
if (arr[j] > arr[j + 1]){
arr[j] = arr[j] + arr[j + 1];
arr[j + 1] = arr[j] - arr[j + 1];
arr[j] = arr[j] - arr[j + 1];
}
}
}
return arr;
}
анализ случая
Взяв в качестве примера массив arr = [3 4 2 8 0], выделенные жирным шрифтом числа представляют собой два числа, которые нужно сравнить в каждом цикле:
первый внешний цикл
( 3 42 8 0 ) → (3 42 8 0 ), 4 > 3 позиция без изменений ( 34 28 0) → (32 48 0 ), 4 > 2 поменять местами ( 3 24 80 ) → ( 3 24 80 ), 8 > 4 позиция без изменений ( 3 2 48 0) → ( 3 2 40 8), 8 > 0 поменять местами
Второй внешний цикл (кроме последнего элемента 8 для оставшейся последовательности)
( 3 24 0 8 ) → (2 34 0 8 ), 3 > 2 поменять местами ( 23 40 8 ) → ( 23 40 8 ), 4 > 3 позиция без изменений ( 2 34 08 ) → ( 2 30 48), 4> 0 поменять позицию
Третий цикл (за исключением двух последних отсортированных элементов, оставшийся цикл до тех пор, пока оставшаяся последовательность не будет равна 1)
( 2 30 4 8 ) → (2 30 4 8 ), 3 > 2 позиция без изменений (23 04 8 ) → (20 34 8 ), 3 > 0 поменять местами
Четвертый внешний цикл (последний раз)
( 2 03 4 8 ) → (0 23 4 8), 2> 0 Положение подкачки
временная сложность и пространственная сложность
Поскольку мы должны повторно выполнять n раз всплытие, каждое всплытие должно выполнять n сравнений (на самом деле арифметическая последовательность от 1 до n, которая равна (a1 + an) * n/2), что составляет O(n^2). Сложность пространства O (1).
Сортировка вставками
Принцип реализации
-
Предположим, что первый элемент отсортирован, и переходим от второго.
-
Возьмите значение текущего элемента и выполните поиск в обратном направлении от отсортированной последовательности.
-
Если элемент в последовательности больше текущего элемента, переместите его назад. пока не найдешь маленькую.
-
Поместите текущий элемент после этого маленького элемента (более поздний элемент больше текущего, он был перемещен назад).
Код
public static int[] insertionSort(int[] arr){
for (int i = 1; i < arr.length; i++) {
for (int j = i; j > 0; j--) {
if (arr[j] < arr[j - 1]){
int temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
}
}
}
return arr;
}
Принципиальная схема
Дело 1
Случай 2
временная сложность и пространственная сложность
N раз из-за выбора, и сравнить худшие вставки n раз, временная сложность также является o (n ^ 2). Сложность пространства O (1).
Сортировка холмов
Принцип реализации
-
Сначала возьмите натуральное число d1 (d1
-
Тогда возьмем d2(d2
-
Повторяйте описанные выше операции группировки и сортировки, пока не будет занята позиция di = 1(i >= 1), то есть все записи станут группой, и, наконец, эта группа будет вставлена и отсортирована. Как правило, d1 равно примерно n/2, d2 равно d1/2, d3 равно d2/2, ..., di = 1.
Код
public static int[] shellSort(int[] arr){
for (int gap = arr.length/2; gap > 0 ; gap/=2) {
for (int i = gap; i < arr.length; i++) {
int j = i;
while (j-gap>=0 && arr[j] < arr[j-gap]){
int temp = arr[j];
arr[j] = arr[j-gap];
arr[j-gap] = temp;
j -= gap;
}
}
}
return arr;
}
анализ случая
Предположим, есть массив array = [80, 93, 85, 10], сначала возьмем D1 = 4, разделим на 4 группы, как показано на рисунке ниже: Группа:
Затем выполните сортировку вставками по 4 группам соответственно, и отсортированные результаты:
Затем возьмите d2 = 2 и разделите исходный массив на 2 группы, как показано ниже:
Затем выполните сортировку вставками по 2 группам соответственно, и отсортированные результаты:
Наконец, возьмите d3 = 1 и выполните сортировку вставками, чтобы получить окончательный результат:
временная сложность и пространственная сложность
На временную сложность сортировки Хилла влияет размер шага, средняя временная сложность составляет O(n log2 n), а пространственная сложность — O(1).
Сортировка слиянием
Принцип реализации
-
Рассматривать n записей как n упорядоченных подсписков длины l
-
Выполнить попарное слияние и упорядочить ключи записи, чтобы получить n/2 упорядоченных подсписков длины 2.
-
Повторяйте шаг 2, пока все записи не будут объединены в упорядоченный список длины n.
В общем, сортировка слиянием заключается в использовании рекурсии, сначала разложении массива на подмассивы, а затем объединении массивов.
Код
public static int[] mergeSort(int[] arr){
int[] temp =new int[arr.length];
internalMergeSort(arr, temp, 0, arr.length-1);
return temp;
}
private static void internalMergeSort(int[] a, int[] b, int left, int right){
//当left==right的时，已经不需要再划分了
if (left<right){
int middle = (left+right)/2;
internalMergeSort(a, b, left, middle); //左子数组
internalMergeSort(a, b, middle+1, right); //右子数组
mergeSortedArray(a, b, left, middle, right); //合并两个子数组
}
}
// 合并两个有序子序列 arr[left, ..., middle] 和 arr[middle+1, ..., right]。temp是辅助数组。
private static void mergeSortedArray(int arr[], int temp[], int left, int middle, int right){
int i=left;
int j=middle+1;
int k=0;
while ( i<=middle && j<=right){
if (arr[i] <=arr[j]){
temp[k++] = arr[i++];
}
else{
temp[k++] = arr[j++];
}
}
while (i <=middle){
temp[k++] = arr[i++];
}
while ( j<=right){
temp[k++] = arr[j++];
}
//把数据复制回原数组
for (i=0; i<k; ++i){
arr[left+i] = temp[i];
}
}
анализ случая
Дело 1
Взяв в качестве примера массив array = [4 2 8 3 5 1 7 6], сначала разделите массив на подмассивы длины 2 и сделайте каждый подмассив упорядоченным:
[4 2] [8 3] [5 1] [7 6] ↓
[2 4] [3 8] [1 5] [6 7]
Затем объедините их по два:
[2 4 3 8] [1 5 6 7] ↓
[2 3 4 8] [1 5 6 7]
Наконец, объедините два подмассива:
[2 3 4 8 1 5 6 7] ↓
[1 2 3 4 5 6 7 8]
Случай 2
временная сложность и пространственная сложность
В процессе объединения массивов фактической операцией является длина двух текущих подмассивов, то есть 2м. А поскольку разбросанный массив разделен на две части, конечное число выполнений цикла равно logn. Таким образом, окончательная временная сложность этого алгоритма равна O(nlogn), а пространственная сложность — O(1).
сортировка кучей
Принцип реализации
Сортировка кучи состоит в том, чтобы вынуть максимальное число в верхней части максимальной кучи, продолжить корректировку оставшейся кучи до максимальной кучи и снова вынуть максимальное число в верхней части кучи.Этот процесс продолжается до тех пор, пока не останется только один оставшийся номер. В куче определены следующие операции:
-
Max-halpify: отрегулируйте дочерние узлы в конце кучи, чтобы узел ребенка всегда меньше, чем родительский узел
-
Build-Max-Heap: переупорядочить все данные в куче, чтобы сделать ее максимальной кучей.
-
Сортировка кучей (Heap-Sort): удалите корневой узел, расположенный в первых данных, и выполните рекурсивную операцию максимальной настройки кучи.
-
Parent(i) = floor((i-1)/2), нижний индекс родительского узла i
-
Left(i) = 2i + 1, индекс левого потомка i
-
Right(i) = 2(i + 1), нижний индекс правого потомка i
Код
/**
* 堆排序
*/
public static int[] heapSort(int[] arr) {
// 将待排序的序列构建成一个大顶堆
for (int i = arr.length / 2; i >= 0; i--){
heapAdjust(arr, i, arr.length);
}
// 逐步将每个最大值的根节点与末尾元素交换，并且再调整二叉树，使其成为大顶堆
for (int i = arr.length - 1; i > 0; i--) {
swap(arr, 0, i); // 将堆顶记录和当前未经排序子序列的最后一个记录交换
heapAdjust(arr, 0, i); // 交换之后，需要重新检查堆是否符合大顶堆，不符合则要调整
}
return arr;
}
/**
* 构建堆的过程
* @param arr 需要排序的数组
* @param i 需要构建堆的根节点的序号
* @param n 数组的长度
*/
private static void heapAdjust(int[] arr, int i, int n) {
int child;
int father;
for (father = arr[i]; leftChild(i) < n; i = child) {
child = leftChild(i);
// 如果左子树小于右子树，则需要比较右子树和父节点
if (child != n - 1 && arr[child] < arr[child + 1]) {
child++; // 序号增1，指向右子树
}
// 如果父节点小于孩子结点，则需要交换
if (father < arr[child]) {
arr[i] = arr[child];
} else {
break; // 大顶堆结构未被破坏，不需要调整
}
}
arr[i] = father;
}
// 获取到左孩子结点
private static int leftChild(int i) {
return 2 * i + 1;
}
// 交换元素位置
private static void swap(int[] arr, int index1, int index2) {
int tmp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = tmp;
}
анализ случая
временная сложность и пространственная сложность
堆执行一次调整需要O(logn)的时间，在排序过程中需要遍历所有元素执行堆调整，所以最终时间复杂度是O(nlogn)。 Сложность пространства O (1).
Эта статья была впервые опубликована на GitChat и не может быть воспроизведена без разрешения. Для перепечатки, пожалуйста, свяжитесь с GitChat.