- 简单排序算法
- 冒泡排序
- 选择排序
- 插入排序
- 快速排序
- 希尔排序
- 归并排序
- 堆排序
- 基数排序
- 排序算法的比较
// 统一辅助函数
public static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
冒泡排序
public static int[] bubbleSort(int[] array) {
// 1：进行n-1趟排序，每次排序将未排序部分的沉底
// 2：每次缩小未排序的部分是length - i - 1
// 进行n - 1次排序
for (int i = 0; i < array.length - 1; i ++) {
// 每次排序的范围
for (int j = 0; j < array.length - i - 1; j ++) {
if (array[j] > array[j + 1]) {
swap(array, j, j + 1);
}
}
}
return array;
}
优化：如果一次冒泡中没有任何的数据交换，就可以说明整个数组已经排好序了，直接结束
public static int[] bubbleSort(int[] array) {
// 1：进行n-1趟排序，每次排序将未排序部分的沉底
// 2：每次缩小未排序的部分是length - i - 1
// 进行n - 1次排序
for (int i = 0; i < array.length - 1; i ++) {
// 每次排序的范围
int flag = 0;
for (int j = 0; j < array.length - i - 1; j ++) {
if (array[j] > array[j + 1]) {
flag = 1;
swap(array, j, j + 1);
}
}
// 如果本次冒泡没有任何的元素变动，则说明整个数组有序
if (flag == 0) {
break;
}
}
return array;
}
选择排序
每次选择未排序中最小的一个，加入到排序队列中的末尾
public static int[] selectorSort(int[] array) {
if (array == null || array.length < ARRAY_LENGTH) {
return array;
}
for (int i = 0; i < array.length - 1; i ++) {
// 初始化当前最小元素所在的位置
int minIndex = i;
// 在 i 到 N - 1 上找最小值的下标
for (int j = i + 1; j < array.length; j ++) {
minIndex = array[j] < array[minIndex] ? j : minIndex;
}
// 找到当前没有排序序列的最小值，然后交换（就是将最小值归位）
swap(array, i, minIndex);
}
return array;
}
插入排序
默认当前的第一个元素是排序的，然后后面的元素像摸扑克牌一样进行插入到指定的位置
public static int[] insertSort(int[] array) {
// 默认第一个数已经排好序了
int sortedIndex = 1;
// 当前要进行插入的数所在的下标
int curIndex = 1;
while (curIndex < array.length) {
// 遍历已经排好序的数组
int i = 0;
while (i < sortedIndex) {
if (array[curIndex] >= array[i]) {
i ++;
} else {
break;
}
}
if (i != sortedIndex) {
// 保存当前的数
int temp = array[curIndex];
// 后移
if (sortedIndex - i >= 0) {
System.arraycopy(array, i, array, i + 1, sortedIndex - i);
}
// 插入
array[i] = temp;
}
curIndex ++;
// 已完成排序的个数 ++
sortedIndex ++;
}
return array;
}
快速排序
private static int[] quickSort(int[] num, int left, int right) {
// ----------------- 下面是一次划分的内容 -----------------------
//如果left等于right，即数组只有一个元素，直接返回
if(left >= right) {
return num;
}
//设置最左边的元素为基准值
int key = num[left];
//数组中比key小的放在左边，比key大的放在右边，key值下标为i
int i = left;
int j = right;
while(i < j) {
// ==== 右哨兵先动！！！！ ======
//j向左移，直到遇到比key小的值
while(num[j] >= key && i < j) {
j --;
}
//i向右移，直到遇到比key大的值
while(num[i] <= key && i < j) {
i ++;
}
//i和j指向的元素交换
if(i < j) {
int temp = num[i];
num[i] = num[j];
num[j] = temp;
}
}
// 基准值归位
num[left] = num[i];
num[i] = key;
// -------------------- 一次划分结束 ----------------
// 递归
quickSort(num, left,i - 1);
quickSort(num,i + 1, right);
return num;
}
希尔排序
public static int[] xierSort(int[] arr) {
//step:步长
for (int step = arr.length / 2; step > 0; step /= 2) {
//对一个步长区间进行比较 [step, arr.length)
for (int i = step; i < arr.length; i++) {
int value = arr[i];
int j;
//对步长区间中具体的元素进行比较
for (j = i - step; j >= 0 && arr[j] > value; j -= step) {
//j为左区间的取值，j+step为右区间与左区间的对应值。
arr[j + step] = arr[j];
}
//此时step为一个负数，[j + step]为左区间上的初始交换值
arr[j + step] = value;
}
}
return arr;
}
归并排序
public static int[] mergeSort(int[] array, int low, int high) {
int mid = (low + high) / 2;
if (low < high) {
// 分
mergeSort(array, low, mid);
mergeSort(array, mid + 1, high);
// 和
merge(array, low, mid, high);
}
return array;
}
public static void merge(int[] a, 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(a[i] < a[j]) {
temp[k++] = a[i++];
} else {
temp[k++] = a[j++];
}
}
// 把左边剩余的数移入数组
while(i <= mid) {
temp[k++] = a[i++];
}
// 把右边边剩余的数移入数组
while(j <= high ) {
temp[k++] = a[j++];
}
// 把新数组中的数覆盖nums数组
for(int x = 0; x < temp.length; x++) {
a[x + low] = temp[x];
}
}
堆排序
- 将无序序列构建成一个堆,根据升序降序需求选择大顶堆或小顶堆;
- 将堆顶元素与末尾元素交换,将最大元素"沉"到数组末端;
- 重新调整结构,使其满足堆定义,然后继续交换堆顶元素与当前末尾元素,反复执行调整+交换步骤,直到整个序列有序。
public static int[] heapSort(int arr[]) {
int temp = 0;
// -- 1. 将无序序列构建成一个堆,根据升序降序需求选择大顶堆或小顶堆; --
for (int i = arr.length / 2 - 1; i >= 0; i--) {
adjustHeap(arr, i, arr.length);
}
for (int j = arr.length - 1; j > 0; j--) {
// -- 2. 将堆顶元素与末尾元素交换,将最大元素"沉"到数组末端; --
temp = arr[j];
arr[j] = arr[0];
arr[0] = temp;
// -- 3. 重新调整结构,使其满足堆定义 --
adjustHeap(arr, 0, j);
}
return arr;
}
public static void adjustHeap(int arr[], int i, int length) {
// 先取出当前元素的值，保存在临时变量
int temp = arr[i];
// 开始调整
// 说明: k=i * 2 + 1, k 是 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] > arr[i]) {
arr[i] = arr[k];
i = k;
} else {
break;
}
}
arr[i] = temp;
}
基数排序
public static int getMax(int[] a) {
int max;
max = a[0];
for (int i = 1; i < a.length; i++) {
if (a[i] > max) {
max = a[i];
}
}
return max;
}
public static void countSort(int[] a, int exp) {
// 存储"被排序数据"的临时数组
int[] output = new int[a.length];
int[] buckets = new int[10];
// 将数据出现的次数存储在buckets[]中
for (int i = 0; i < a.length; i++) {
buckets[(a[i] / exp) % 10]++;
}
// 更改buckets[i]。目的是让更改后的buckets[i]的值，是该数据在output[]中的位置。
for (int i = 1; i < 10; i++) {
buckets[i] += buckets[i - 1];
}
// 将数据存储到临时数组output[]中
for (int i = a.length - 1; i >= 0; i--) {
output[buckets[(a[i] / exp) % 10] - 1] = a[i];
buckets[(a[i] / exp) % 10]--;
}
// 将排序好的数据赋值给a[]
for (int i = 0; i < a.length; i++) {
a[i] = output[i];
}
}
public static int[] radixSort(int[] a) {
// 指数。当对数组按各位进行排序时，exp=1；按十位进行排序时，exp=10；...
int exp;
int max = getMax(a);
// 从个位开始，对数组a按"指数"进行排序
for (exp = 1; max / exp > 0; exp *= 10) {
countSort(a, exp);
}
return a;
}
排序算法的比较
