排序之冒泡排序
原理：比较相邻的元素，将大的元素放右边，小的元素放左边。每一趟排的最后的元素一定是最大的元素，所有下一趟需要排列的元素可减少一个
public int[] bubbleSort(int[] attr) {
for (int i = 0; i < attr.length - 1; i++) {
for (int j = 0; j < attr.length - 1-i; j++) {
if (attr[j] > attr[j + 1]) {
int t = attr[j + 1];
attr[j + 1] = attr[j];
attr[j] = t;
}
}
}
return attr;
}
public class OptimizedBubbleSort {
public static void bubbleSort(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
boolean isSorted = true; // 有序标记，初始为true
int n = arr.length;
int lastSwapIndex = n - 1; // 初始化最后交换位置为数组末尾
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < lastSwapIndex; j++) {
if (arr[j] > arr[j + 1]) {
// 交换相邻元素
swap(arr, j, j + 1);
isSorted = false; // 发生交换，数组未完全有序
lastSwapIndex = j; // 更新最后交换位置
}
}
// 如果一轮比较没有发生交换，说明数组已经有序
if (isSorted) {
break;
}
}
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
int[] arr = {5, 2, 9, 1, 5, 6};
System.out.println("排序前: " + Arrays.toString(arr));
bubbleSort(arr);
System.out.println("排序后: " + Arrays.toString(arr));
}
}
排序之简单选择排序
每次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
第一层循环从起始元素开始选到倒数第二个元素，主要是在每次进入的第二层循环之前，将外层循环的下标赋值给临时变量，接下来的第二层循环中，如果发现有比这个最小位置处的元素更小的元素，则将那个更小的元素的下标赋给临时变量，最后，在二层循环退出后，如果临时变量改变，则说明，有比当前外层循环位置更小的元素，需要将这两个元素交换.
选择排序的时间复杂度：简单选择排序的比较次数与序列的初始排序无关。 假设待排序的序列有 N 个元素，则比较次数永远都是N (N - 1) / 2。而移动次数与序列的初始排序有关。当序列正序时，移动次数最少，为 0。当序列反序时，移动次数最多，为3N (N - 1) / 2。
所以，综上，简单排序的时间复杂度为 O(N2)。
public int[] select(int[] s) {
for (int i = 0; i < s.length - 1; i++) {
int k = i;
for (int n = i + 1; n < s.length; n++) {
if (s[k] > s[n]) {
k = n;
}
}
if (i != k) {
int a = s[i];
s[i] = s[k];
s[k] = a;
}
}
return s;
}
排序之快速排序
原理：采用“分而治之”的思想，对于给定的数组attr，选择一个基准元素，通常选择第一个元素或者最后一个元素，将基准元素看成一个“坑”，i指针指向数组第一个元素，j指针指向数组最后一个元素，若基准元素是第一个attr[0]，则先j开始往前寻找小于或等于基准元素的元素，则将attr[j]和基准元素交换，j–，基准元素变成attr[j],然后从i开始往后寻找大于基准元素的元素，则将attr[j]和基准元素交换。直到i==j 一轮排序介绍，基准元素的左边色元素都比它小，右边的都比它大，将数组分为两部分再次按同样的思想排序
void quick_sort(int s[], int first, int end) {
if (first < end) {
int i = first, j = end, x = s[first];
while (i < j) {
while (i < j && s[j] >= x) // 从右向左找第一个小于x的数
j--;
if (i < j)
s[i++] = s[j];
while (i < j && s[i] < x) // 从左向右找第一个大于等于x的数
i++;
if (i < j)
s[j--] = s[i];
}
s[i] = x;
quick_sort(s, first, i - 1); // 递归调用
quick_sort(s, i + 1, end);
}
}
import java.util.Arrays;
import java.util.Random;
public class RandomizedQuickSort {
public static void quickSort(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
sort(arr, 0, arr.length - 1);
}
private static void sort(int[] arr, int low, int high) {
if (low < high) {
// 随机选择pivot并分区
int pivotIndex = partition(arr, low, high);
// 递归排序分区
sort(arr, low, pivotIndex - 1);
sort(arr, pivotIndex + 1, high);
}
}
private static int partition(int[] arr, int low, int high) {
// 1. 随机选择pivot并交换到首位
int randomIndex = getRandomIndex(low, high);
swap(arr, low, randomIndex);
int pivot = arr[low]; // 基准值
// 2. 双指针分区
int i = low + 1; // 从左向右找大于pivot的元素
int j = high; // 从右向左找小于pivot的元素
while (i <= j) {
// 找到左边第一个大于pivot的元素
while (i <= j && arr[i] <= pivot) {
i++;
}
// 找到右边第一个小于pivot的元素
while (i <= j && arr[j] > pivot) {
j--;
}
if (i < j) {
swap(arr, i, j);
}
}
// 3. 将pivot放到正确位置
swap(arr, low, j);
return j;
}
// 生成low到high之间的随机索引
private static int getRandomIndex(int low, int high) {
Random rand = new Random();
return low + rand.nextInt(high - low + 1);
}
// 交换数组元素
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
int[] arr = {9, 7, 5, 11, 12, 2, 14, 3, 10, 6};
System.out.println("排序前: " + Arrays.toString(arr));
quickSort(arr);
System.out.println("排序后: " + Arrays.toString(arr));
}
}
import java.util.Random;
public class QuickSort {
// 主方法：对外暴露的排序接口
public static void quickSort(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
sort(arr, 0, arr.length - 1);
}
// 递归排序核心逻辑
private static void sort(int[] arr, int left, int right) {
if (left >= right) {
return; // 递归终止条件
}
// 随机选择 pivot 并分区，返回分区后的 pivot 索引
int pivotIndex = partition(arr, left, right);
// 递归排序左半部分和右半部分
sort(arr, left, pivotIndex - 1);
sort(arr, pivotIndex + 1, right);
}
// 分区操作：随机选择 pivot，并将数组分为两部分
private static int partition(int[] arr, int left, int right) {
// 随机生成 pivot 索引（范围: [left, right]）
int randomPivotIndex = left + new Random().nextInt(right - left + 1);
// 将随机选中的 pivot 交换到数组末尾（标准分区做法）
swap(arr, randomPivotIndex, right);
int pivot = arr[right]; // pivot 值
int i = left; // i 是小于 pivot 的元素的边界
// 遍历数组，将小于 pivot 的元素移到左侧
for (int j = left; j < right; j++) {
if (arr[j] < pivot) {
swap(arr, i, j); // 交换当前元素到左半部分
i++;
}
}
// 将 pivot 放到正确位置（i 的右侧）
swap(arr, i, right);
return i; // 返回 pivot 的最终位置
}
// 交换数组中两个元素的位置
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// 测试代码
public static void main(String[] args) {
int[] arr = {3, 6, 8, 10, 1, 2, 1};
System.out.println("排序前: " + Arrays.toString(arr));
quickSort(arr);
System.out.println("排序后: " + Arrays.toString(arr));
}
}
排序之堆排序
堆的定义如下：n个元素的序列{k1,k2,…,kn}，当且仅满足ki<=k2i &&ki<=k2i+1 或者 ki>=k2i && ki>=k2i+1 的关系时，称之为堆。
//构建大根堆：将array看成完全二叉树的顺序存储结构
private int[] buildMaxHeap(int[] array) {
//从最后一个节点array.length-1的父节点（array.length-1-1）/2开始，直到根节点0，反复调整堆
for (int i = (array.length - 2) / 2; i >= 0; i--) {
adjustDownToUp(array, i, array.length);
}
return array;
}
//将元素array[k]自下往上逐步调整树形结构
private void adjustDownToUp(int[] array, int k, int length) {
int temp = array[k];
for (int i = 2 * k + 1; i < length - 1; i = 2 * i + 1) { //i为初始化为节点k的左孩子，沿节点较大的子节点向下调整
if (i < length && array[i] < array[i + 1]) { //取节点较大的子节点的下标
i++; //如果节点的右孩子>左孩子，则取右孩子节点的下标
}
if (temp >= array[i]) { //根节点 >=左右子女中关键字较大者，调整结束
break;
} else { //根节点 <左右子女中关键字较大者
array[k] = array[i]; //将左右子结点中较大值array[i]调整到双亲节点上
k = i; //【关键】修改k值，以便继续向下调整
}
}
array[k] = temp; //被调整的结点的值放人最终位置
}
//堆排序
public int[] heapSort(int[] array) {
array = buildMaxHeap(array); //初始建堆，array[0]为第一趟值最大的元素
for (int i = array.length - 1; i > 1; i--) {
int temp = array[0]; //将堆顶元素和堆低元素交换，即得到当前最大元素正确的排序位置
array[0] = array[i];
array[i] = temp;
adjustDownToUp(array, 0, i); //整理，将剩余的元素整理成堆
}
return array;
}