排序算法主要有：插入排序，选择排序，冒泡排序，希尔排序，归并排序，快速排序，堆排序。这里的排序指的是内部排序，也就是基于内存的排序，基于内存的排序是基于大O模型的，可以使用大O模型来衡量算法的性能
Взято из моего собственного сада блога:Блог Woohoo.cn на.com/no admin/afraid/5…Алгоритм частичной сортировки в .
Сортировка вставками
Основная идея: вставлять часть данных, подлежащих сортировке по размеру, в соответствующую позицию в отсортированных данных на каждом шаге, пока все вставки не будут завершены.
原始：4 3 1 2
1) 3 4 1 2
2) 1 3 4 2
3) 1 2 3 4Основной код:
/**
* 插入排序
*/
public static int[] insertSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int index = i;// index当前扫描到的元素下标
int temp = arr[i];
// 寻找插入的位置
while (index > 0 && temp < arr[index - 1]) {
arr[index] = arr[index - 1];
index--;
}
arr[index] = temp;
}
return arr;
}сортировка выбором
Основная идея: найти наименьшую из всех последовательностей и поставить ее на первое место. Затем посмотрите на самый маленький из оставшихся элементов и поставьте его на вторую позицию... и так далее, можно завершить всю работу по сортировке. Ясно видно, что сортировка выбором — это фиксированная позиция для поиска элементов. По сравнению с фиксированным элементом сортировки вставками, чтобы найти позицию, есть два способа мышления.
3 2 1 4 6 5
初始化索引位置为0
寻找最小值所在位置交换：1 2 3 4 6 5
初始化索引位置为1
寻找最小值所在位置交换：1 2 3 4 6 5
依次类推！Основной код:
/**
* 选择排序
*/
public static int[] selectSort(int[] arr) {
for (int i = 0; i < arr.length; i++) {
int minVal = arr[i];
int index = i;
for (int j = i + 1; j < arr.length; j++) {// 找到最小元素
if (arr[j] < minVal) {
minVal = arr[j];
index = j;
}
}
arr[index] = arr[i];
arr[i] = minVal;
}
return arr;
}Пузырьковая сортировка
Основная идея: Принцип состоит в том, чтобы сравнивать соседние числа попарно и менять их местами в порядке от меньшего к большему или от большего к меньшему.
Основной код:
/**
* 冒泡排序
*
* @param arr
* 输入的待排数组
* @return 返回排序号的数组
*/
public static int[] bubbleSort(int[] arr) {
for (int i = 0; i < arr.length; i++) {
for (int j = 1; j < arr.length; j++) {
if (arr[j - 1] > arr[j]) {
int temp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = temp;
}
}
}
return arr;
}Сортировка холмов
Основная идея: сначала взять целое число d1 меньше n в качестве первого приращения и сгруппировать все записи файла. Все записи с расстояниями, кратными d1, помещаются в одну группу. Сначала выполнить сортировку прямым вставкой в каждой группе, затем взять второе приращение d2 Основной код: Основная идея: рассматривать последовательность для сортировки R[0...n-1] как n упорядоченных последовательностей длины 1, объединять соседние упорядоченные списки попарно и получать n/2 последовательностей длины 2 Упорядоченная таблица, снова объединять эти упорядоченные последовательности чтобы получить n/4 упорядоченных последовательностей длины 4, и так далее, и, наконец, получить упорядоченную последовательность длины n. Основной код: Основная идея: Идея, принятая быстрой сортировкой, — это идея «разделяй и властвуй». Основной код:/**
* 希尔排序
*
* @author sgl
*
*/
public class ShellSort {
public static int[] shellSort(int[] arr) {
int step = arr.length / 2;// 初始步长
while (1 <= step) {
for (int i = step; i < arr.length; i++) {
if (arr[i] < arr[i - step]) {
int temp = arr[i];
arr[i] = arr[i - step];
arr[i - step] = temp;
}
}
step = step / 2;
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]+",");
}
System.out.println();
}
return arr;
}Сортировка слиянием
Сортировка слиянием на самом деле делает две вещи:
(1) «Разложение» — каждый раз делите последовательность пополам.
(2) «Объединить» — объединить разделенные сегменты последовательности попарно, а затем отсортировать их.public static int[] sort(int[] nums, int low, int high) {
int mid = (low + high) / 2;
if (low < high) {
sort(nums, low, mid);// 左边
sort(nums, mid + 1, high);// 右边
merge(nums, low, mid, high);// 左右归并
}
return nums;
}
public static void merge(int[] nums, int low, int mid, int high) {
int[] temp = new int[high - low + 1];
int i = low;// 左指针
int j = mid + 1;// 右指针
int k = 0;
// 把较小的数先移到新数组中
while (i <= mid && j <= high) {
if (nums[i] < nums[j]) {
temp[k++] = nums[i++];
} else {
temp[k++] = nums[j++];
}
}
// 把左边剩余的数移入数组
while (i <= mid) {
temp[k++] = nums[i++];
}
// 把右边边剩余的数移入数组
while (j <= high) {
temp[k++] = nums[j++];
}
// 把新数组中的数覆盖nums数组
for (int k2 = 0; k2 < temp.length; k2++) {
nums[k2 + low] = temp[k2];
}
}
}быстрая сортировка
Быстрая сортировка заключается в том, чтобы найти элемент (теоретически можно найти любой) в качестве эталона, а затем выполнить операцию разбиения массива так, чтобы значение элемента слева от эталона не было больше эталонного значение, а значение элемента в правой части эталона не меньше эталонного значения, т.к. элементы данных корректируются в правильное положение после сортировки. Рекурсивная быстрая сортировка, после сортировки настройте другие элементы n-1 на правильное положение. Наконец, каждый элемент находится в правильном положении после сортировки, и сортировка завершена. Таким образом, основным алгоритмом алгоритма быстрой сортировки является операция разделения, то есть, как настроить положение данных и скорректировать конечное положение возвращенных данных для рекурсии «разделяй и властвуй»./**
* 快速排序
*
* @author sgl
*
*/
public class QuickSort {
static void quicksort(int n[], int left, int right) {
int dp;
if (left < right) {
dp = partition(n, left, right);
quicksort(n, left, dp - 1);
quicksort(n, dp + 1, right);
}
}
static int partition(int n[], int left, int right) {
int pivot = n[left];
while (left < right) {
while (left < right && n[right] >= pivot)
right--;
if (left < right)
n[left++] = n[right];
while (left < right && n[left] <= pivot)
left++;
if (left < right)
n[right--] = n[left];
}
n[left] = pivot;
return left;
}
}