经典排序算法图
排序算法.png
- 冒泡排序
通过比较相邻两个元素，比较大小，交换位置，把最大或最小的元素放到序列最后
public static void sort(int[] array) {
if (array == null || array.length == 0) {
return;
}
int length = array.length;
for (int i = 0; i < length - 1; i++) {
for (int j = 0; j < length - 1 - i; j++) {
if (array[j] > array[j + 1]) {
array[j] = array[j] + array[j + 1];
array[j + 1] = array[j] - array[j + 1];
array[j] = array[j] - array[j + 1];
}
}
}
}
- 快速排序
将无序序列递归拆分为2个子序列，在每个序列找出一个基准值，每个元素跟基准值对比，小于基准值，放在左边，大于基准值的放在右边
public static void sort(int[] array, int low, int high) {
if (array == null || array.length == 0) {
return;
}
if (low >= high) {
return;
}
int left = low;
int right = high;
int key = array[left];
while (left < right) {
while (left < right && array[right] >= key) {
right--;
}
while (left < right && array[left] <= key) {
left++;
}
if (left < right) {
swap(array, left, right);
}
}
swap(array, low, left);
sort(array, low, left - 1);
sort(array, left + 1, high);
}
public static void swap(int array[], int low, int high) {
int temp = array[low];
array[low] = array[high];
array[high] = temp;
}
- 插入排序
默认将无序序列第一个为有序的，后面的元素在前面的序列找到一个合适的位置插入
public static void sort(int[] array) {
if (array == null || array.length == 0) {
return;
}
for (int i = 1; i < array.length; i++) {
int j = i - 1;
int temp = array[i];
while (j >= 0 && temp < array[j]) {
array[j + 1] = array[j];
j--;
}
array[j + 1] = temp;
}
}
- 希尔排序
将无序序列按步长分组，对每个组进行插入排序，直到步长为1，步长可用序列长度的一半
public static void sort(int[] array) {
if (array == null || array.length == 0) {
return;
}
int gap = array.length / 2;
for (; gap > 0; gap /= 2) {
for (int j = 0; j < gap; j++) {
for (int i = 0; i + gap < array.length; i += gap) {
if (array[i] > array[i + gap]) {
array[i] = array[i] + array[i + gap];
array[i + gap] = array[i] - array[i + gap];
array[i] = array[i] - array[i + gap];
}
}
}
}
}
- 简单选择排序
在无序序列找出最大或最小的元素，跟第一个位置对比，交换位置，接着继续找剩余最大或最小的元素，再跟剩余的第一个位置对比交换
public static void sort(int[] array) {
if (array == null || array.length == 0) {
return;
}
int minIndex = 0;
for (int i = 0; i < array.length; i++) {
minIndex = i;
for (int j = i; j < array.length; j++) {
if (array[j] < array[minIndex]) {
minIndex = j;
}
}
if (i != minIndex) {
array[i] = array[i] + array[minIndex];
array[minIndex] = array[i] - array[minIndex];
array[i] = array[i] - array[minIndex];
}
}
}
- 堆排序
将无序序列转为大顶堆或小顶堆，接着将顶堆元素跟最后一个元素对比，交换位置，接着重新调整堆结构
public static void sort(int[] array) {
for (int i = array.length / 2 - 1; i >= 0; i--) {
adjustHeap(array, i, array.length);
}
for (int j = array.length - 1; j > 0; j--) {
swap(array, 0, j);
adjustHeap(array, 0, j);
}
}
public static void adjustHeap(int[] arr, int i, int length) {
int temp = arr[i];
for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
if (k + 1 < length && arr[k] < arr[k + 1]) {
k++;
}
if (arr[k] > temp) {
arr[i] = arr[k];
i = k;
} else {
break;
}
}
arr[i] = temp;
}
public static void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
- 归并排序
将无序序列拆分为若干个子序列，每两个子序列进行比较大小，组成有序子序列，每个子序列都是有序的，最后将每个子序列合并为有序序列
public static int[] sort(int[] array) {
if (array.length <= 1) {
return array;
}
int temp = array.length >> 1;
int[] left = Arrays.copyOfRange(array, 0, temp);
int[] right = Arrays.copyOfRange(array, temp, array.length);
return mergeArray(sort(left), sort(right));
}
public static int[] mergeArray(int[] left, int[] right) {
int i = 0, j = 0, k = 0;
int[] result = new int[left.length + right.length];
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
result[k++] = left[i++];
} else {
result[k++] = right[j++];
}
}
while (i < left.length) {
result[k++] = left[i++];
}
while (j < right.length) {
result[k++] = right[j++];
}
return result;
}
- 基数排序
将无序序列每个元素调整为固定长度，不足长度的，前面补0，接着从低位开始，把低位的元素进入指定的桶（数组），然后重新组成新的序列，直到最高位排完
public static void sort(int[] array) {
if (array == null || array.length == 0) {
return;
}
int max = array[0];
for (int i = 1; i < array.length; i++) {
if (array[i] > max) {
max = array[i];
}
}
int num = 0;
while (max != 0) {
max = max / 10;
num++;
}
int[][] result = new int[10][array.length];
int base = 1;
for (int i = 0; i < num; i++) {
int[] bucket = new int[10];
int whichBucket = 0;
int bucketLength = 0;
for (int j = 0; j < array.length; j++) {
whichBucket = (array[j] / base) % 10;
bucketLength = bucket[whichBucket];
result[whichBucket][bucketLength] = array[j];
bucket[whichBucket] = bucketLength + 1;
}
int index = 0;
for (int j = 0; j < result.length; j++) {
for (int k = 0; k < bucket[j]; k++) {
array[index++] = result[j][k];
}
}
base *= 10;
}
}
