# 经典排序算法总结--冒泡、快排、插入、希尔、归并、选择

2016年11月16日 发布，来源：geek.csdn.net

``````public static void bubbleSort(int[] arr, int size) {
boolean swap = false;
for (int i = 0; i < size - 1; i++) { //最多进行 n-1 趟
swap = false;
for (int j = size - 1; j > i; j--) { //从下往上扫描
if (arr[j] < arr[j - 1]) {
swap(arr, j, j - 1);
swap = true;
}
}
if (!swap) {
break; // 未发生交换，终止算法
}
}
}``````

``````public static void swap(int[] arr, int one, int two) {
int temp = arr[one];
arr[one] = arr[two];
arr[two] = temp;
}``````

``````// 排序范围 [start, end], 包含 end
public static void quickSort(int[] arr, int start, int end) {
if (start < end) {
int p = partition(arr, start, end);
quickSort(arr, start, p - 1);
quickSort(arr, p + 1, end);
}
}
// 一次划分代码，返回被划分后的基准位置
public static int partition(int[] arr, int left, int right) {
int pivot = arr[left];
while (left < right) {
while (left < right && arr[right] >= pivot)
right--;
if (left < right)
arr[left++] = arr[right];
while (left < right && arr[left] <= pivot)
left++;
if (left < right)
arr[right--] = arr[left];
}
arr[left] = pivot;
return left;
}``````

``````public static void quickSort(int[] arr, int start, int end) {
int[] stack = new int[end - start + 1]; // 数组模拟栈
int len = 0;
stack[len++] = start; // 入栈
stack[len++] = end;
while (len > 0) { // 栈中还有元素
int right = stack[--len]; // 注意是 --len
int left = stack[--len];
int p = partition(arr, left, right);
if (p - 1 > left) {
stack[len++] = left;
stack[len++] = p - 1;
}
if (p + 1 < right) {
stack[len++] = p + 1;
stack[len++] = right;
}
}
}``````

``````public static void insertSort(int[] arr, int size) {
int temp = arr[0];
for (int i = 1; i < size; i++) {
// 若 arr[i] 不小于有序区的最后一个元素，直接扩大有序区
if (arr[i] < arr[i - 1]) {
temp = arr[i];
int j = i - 1;
while (j >= 0 && temp < arr[j]) {
arr[j + 1] = arr[j--];
}
arr[j + 1] = temp;
}
}
}``````

``````// shellSort(origins, origins.length, new int[] { 5, 3, 1 });
public static void shellSort(int[] arr, int size, int[] d) {
for (int k = 0; k < d.length; k++) {
int gap = d[k];
for (int j = 0; j < gap; j++) { // 对于增量值 gap，一共 gap 组，0~gap-1
for (int i = j + gap; i < size; i++) {
if (arr[i] < arr[i - gap]) { // 如果大于，不需要插入排序
int pivot = arr[i];
int t = i - gap;
while (t >= 0 && pivot < arr[t]) {
arr[t + gap] = arr[t];
t = t - gap;
}
arr[t + gap] = pivot;
}
}
}
}
}``````

``````// 将arr[low]~arr[center]与arr[center+1]~arr[right]合并成有序表
public static void merge(int[] arr, int left, int center, int right) {
int[] result = new int[right - left + 1];
int i = left, j = center + 1, k = 0;
while (i <= center && j <= right) {
if (arr[i] < arr[j])
result[k++] = arr[i++];
else
result[k++] = arr[j++];
}
while (i <= center)
result[k++] = arr[i++];
while (j <= right)
result[k++] = arr[j++];
System.arraycopy(result, 0, arr, left, right - left + 1);
}``````

arr[0]~arr[step-1], arr[step]~arr[step*2-1], ··· ，一趟归并将相邻的一对有序表进行归并。

• 有序表的个数为偶数，且长度均为step
• 有序表的个数为偶数，但最后一个有序表的长度小于step
• 有序表的个数为奇数（轮空，不需要归并）
``````// 子表的长度为 step，对数组进行一趟归并
public static void mergePass(int[] arr, int step) {
int length = arr.length;
int i = 0;
// 循环，归并长度为 step 的两个有序表
for (; i + step * 2 - 1 < length; i += step * 2) {
merge(arr, i, i + step - 1, i + step * 2 - 1);
}
if (i + step < length)
merge(arr, i, i + step - 1, length - 1);
// 注意: 若 i + step >= length, 最后一个子表轮空，无需归并
}``````

``````public static void mergeSort(int[] arr, int size) {
for (int i = 1; i < size; i *= 2) {
mergePass(arr, i);
}
}``````

``````public static void selectSort(int[] arr, int size) {
for (int i = 0; i < size; i++) {
int min = i;
for (int j = i + 1; j < size; j++) {
if (arr[j] < arr[min])
min = j;
}
if (min != i)
swap(arr, min, i);
}
}``````

1.7k 浏览 432 收藏 报告 阅读模式
1 条评论
huangjj27 · 2016年11月16日