- /**
- * 冒泡排序:* 比较相邻的元素。如果第一个比第二个大,就交换他们两个。* 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。* 针对所有的元素重复以上的步骤,除了最后一个。* 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。*/
- public class BubbleSort {
- public static void main(String[] args) {
- int[] arr = new int[]{3, 4, 5, 7, 1, 2, 0, 3, 6, 8};
- System.out.printf("排序前:" + Arrays.toString(arr) + "\n");
- bubbleSort(arr);
- System.out.printf("排序后:" + Arrays.toString(arr));
- }
-
-
- public static void bubbleSort(int[] arr) {
- for (int i = 0; i < arr.length - 1; i++) {
- for (int j = 0; j < arr.length - 1 - i; j++) {
- if (arr[j] > arr[j + 1]) {
- int temp = arr[j];
- arr[j] = arr[j + 1];
- arr[j + 1] = temp;
- }
- }
- }
- }
- }
- /**
- * 快速排序:* 快速排序的核心思想也是分治法,分而治之。* 选取第一个数为基准,将比基准小的数交换到前面,比基准大的数交换到后面,对左右区间重复第二步,直到各区间只有一个数
- */
- public class QuickSort {
- public static void main(String[] args) {
- int[] arr = new int[]{3, 4, 5, 7, 1, 2, 0, 3, 6, 8};
- System.out.printf("排序前:" + Arrays.toString(arr) + "\n");
- quickSort(arr, 0, arr.length - 1);
- System.out.printf("排序后:" + Arrays.toString(arr));
- }
-
-
- public static void quickSort(int[] arr, int low, int high) {
- int i, j, temp, t;
- if (low > high) {
- return;
- }
- i = low;
- j = high;
- //temp就是基准位
- temp = arr[low];
-
- while (i < j) {
- //从右往左扫描,找到第一个比基准值小的元素
- while (temp <= arr[j] && i < j) {
- j--;
- }
- //从左往右扫描,找到第一个比基准值大的元素
- while (temp >= arr[i] && i < j) {
- i++;
- }
- //如果满足条件则交换
- if (i < j) {
- t = arr[j];
- arr[j] = arr[i];
- arr[i] = t;
- }
- }
- //最后将基准为与i和j相等位置的数字交换
- arr[low] = arr[i];
- arr[i] = temp;
- //递归调用左半数组
- quickSort(arr, low, j - 1);
- //递归调用右半数组
- quickSort(arr, j + 1, high);
- }
- }
- /**
- * 插入排序:* 从第一个元素开始,该元素可以认为已经被排序
- * 取出下一个元素,在已经排序的元素序列中从后向前扫描
- * 如果该元素(已排序)大于新元素,将该元素移到下一位置
- * 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
- * 将新元素插入到该位置后
- * 重复步骤2~5
- * 插入排序的思想和我们打扑克摸牌的时候一样,从牌堆里一张一张摸起来的牌都是乱序的,我们会把摸起来的牌插入到左手中合适的位置,让左手中的牌时刻保持一个有序的状态。*/
- public class InsertSort {
- public static void main(String[] args) {
- int[] arr = new int[]{3, 4, 5, 7, 1, 2, 0, 3, 6, 8};
- System.out.printf("排序前:" + Arrays.toString(arr) + "\n");
- insertSort(arr);
- System.out.printf("排序后:" + Arrays.toString(arr));
- }
-
-
- public static void insertSort(int[] arr) {
- for (int i = 1; i < arr.length; i++) {
- if (arr[i] < arr[i - 1]) {
- int temp = arr[i];
- int j; //插入的位置
- for (j = i - 1; j >= 0 && temp < arr[j]; j--) {
- arr[j + 1] = arr[j]; //移动数据
- }
- arr[j + 1] = temp; //插入数据
- }
- }
- }
- }
- /**
- * 选择排序:* 在未排序序列中找到最小(大)元素,存放到排序序列的起始位置
- * 从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾
- * 以此类推,直到所有元素均排序完毕
- */
- public class SelectSort {
- public static void main(String[] args) {
- int[] arr = new int[]{3, 4, 5, 7, 1, 2, 0, 3, 6, 8};
- System.out.printf("排序前:" + Arrays.toString(arr) + "\n");
- selectsort(arr);
- System.out.printf("排序后:" + Arrays.toString(arr));
- }
-
-
- public static void selectsort(int[] arr) {
- for (int i = 0; i < arr.length; i++) {
- int min = i; //最小元素的下标
- for (int j = i + 1; j < arr.length; j++) {
- if (arr[min] > arr[j]) {
- min = j; //找最小值
- }
- }
- //交换位置
- if (i != min) {
- int temp = arr[i];
- arr[i] = arr[min];
- arr[min] = temp;
- }
- }
- }
- }
- /**
- * 堆排序:* 1、根据初始数组构造堆
- * 2、每次交换第一个和最后一个元素,然后将除最后一个元素以外的其他元素重新调整为大顶堆
- * 重复以上两个步骤,直到没有元素可操作,就完成排序了。*/
- public class HeapSort {
- public static void main(String[] args) {
- int[] arr = new int[]{3, 4, 5, 7, 1, 2, 0, 3, 6, 8};
- System.out.printf("排序前:" + Arrays.toString(arr) + "\n");
- heapSort(arr);
- System.out.printf("排序后:" + Arrays.toString(arr));
- }
-
-
- /**
- * 转化为大顶堆
- * @param arr 待转化的数组
- * @param size 待调整的区间长度
- * @param index 结点下标
- */
- public static void maxHeap(int[] arr, int size, int index) {
- //左子结点
- int leftNode = 2 * index + 1;
- //右子结点
- int rightNode = 2 * index + 2;
- int max = index;
- //和两个子结点分别对比,找出最大的结点
- if (leftNode < size && arr[leftNode] > arr[max]) {
- max = leftNode;
- }
- if (rightNode < size && arr[rightNode] > arr[max]) {
- max = rightNode;
- }
- //交换位置
- if (max != index) {
- int temp = arr[index];
- arr[index] = arr[max];
- arr[max] = temp;
- //因为交换位置后有可能使子树不满足大顶堆条件,所以要对子树进行调整
- maxHeap(arr, size, max);
- }
- }
-
-
- public static void heapSort(int[] arr) {
- //开始位置是最后一个非叶子结点,即最后一个结点的父结点
- int start = (arr.length - 1) / 2;
- //调整为大顶堆
- for (int i = start; i >= 0; i--) {
- HeapSort.maxHeap(arr, arr.length, i);
- }
- //先把数组中第 0 个位置的数和堆中最后一个数交换位置,再把前面的处理为大顶堆
- for (int i = arr.length - 1; i > 0; i--) {
- int temp = arr[0];
- arr[0] = arr[i];
- arr[i] = temp;
- maxHeap(arr, i, 0);
- }
- }
- }
- /**
- * 归并排序:* 将 n 个元素分成两个各含 n/2 个元素的子序列
- * 借助递归,两个子序列分别继续进行第一步操作,直到不可再分为止
- * 此时每一层递归都有两个子序列,再将其合并,作为一个有序的子序列返回上一层,再继续合并,全部完成之后得到的就是一个有序的序列
- * 关键在于两个子序列应该如何合并。假设两个子序列各自都是有序的,那么合并步骤就是:* 创建一个用于存放结果的临时数组,其长度是两个子序列合并后的长度
- * 设定两个指针,最初位置分别为两个已经排序序列的起始位置
- * 比较两个指针所指向的元素,选择相对小的元素放入临时数组,并移动指针到下一位置
- * 重复步骤 3 直到某一指针达到序列尾
- * 将另一序列剩下的所有元素直接复制到合并序列尾
- */
- public class MergeSort {
- public static void main(String[] args) {
- int[] arr = new int[]{3, 4, 5, 7, 1, 2, 0, 3, 6, 8};
- System.out.printf("排序前:" + Arrays.toString(arr) + "\n");
- mergeSort(arr, 0, arr.length - 1);
- System.out.printf("排序后:" + Arrays.toString(arr));
- }
-
-
- /**
- * 合并数组
- */
- public static void merge(int[] arr, int low, int middle, int high) {
- // 用于存储归并后的临时数组
- int[] temp = new int[high - low + 1];
- // 记录第一个数组中需要遍历的下标
- int i = low;
- // 记录第二个数组中需要遍历的下标
- int j = middle + 1;
- // 记录在临时数组中存放的下标
- int index = 0;
- // 遍历两个数组,取出小的数字,放入临时数组中
- while (i <= middle && j <= high) {
- // 第一个数组的数据更小
- if (arr[i] <= arr[j]) {
- // 把更小的数据放入临时数组中
- temp[index] = arr[i];
- // 下标向后移动一位
- i++;
- } else {
- temp[index] = arr[j];
- j++;
- }
- index++;
- }
- // 处理剩余未比较的数据
- while (i <= middle) {
- temp[index] = arr[i];
- i++;
- index++;
- }
- while (j <= high) {
- temp[index] = arr[j];
- j++;
- index++;
- }
- // 把临时数组中的数据重新放入原数组
- for (int k = 0; k < temp.length; k++) {
- arr[k + low] = temp[k];
- }
- }
-
-
- /**
- * 归并排序
- */
- public static void mergeSort(int[] arr, int low, int high) {
- int middle = (high + low) / 2;
- if (low < high) {
- // 处理左边数组
- mergeSort(arr, low, middle);
- // 处理右边数组
- mergeSort(arr, middle + 1, high);
- // 归并
- merge(arr, low, middle, high);
- }
- }
- }
- /**
- * 基数排序:* 基数排序的原理是将整数按位数切割成不同的数字,然后按每个位数分别比较
- * 为此需要将所有待比较的数值统一为同样的数位长度,数位不足的数在高位补零
- */
- public class RadixSort {
- public static void main(String[] args) {
- int[] arr = new int[]{3, 4, 5, 7, 1, 2, 0, 3, 6, 8};
- System.out.printf("排序前:" + Arrays.toString(arr) + "\n");
- radixSort(arr);
- System.out.printf("排序后:" + Arrays.toString(arr));
- }
-
-
- /**
- * 基数排序
- */
- public static void radixSort(int[] arr) {
- // 存放数组中的最大数字
- int max = Integer.MIN_VALUE;
- for (int value : arr) {
- if (value > max) {
- max = value;
- }
- }
- // 计算最大数字是几位数
- int maxLength = (max + "").length();
- // 用于临时存储数据
- int[][] temp = new int[10][arr.length];
- // 用于记录在 temp 中相应的下标存放数字的数量
- int[] counts = new int[10];
- // 根据最大长度的数决定比较次数
- for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
- // 每一个数字分别计算余数
- for (int j = 0; j < arr.length; j++) {
- // 计算余数
- int remainder = arr[j] / n % 10;
- // 把当前遍历的数据放到指定的数组中
- temp[remainder][counts[remainder]] = arr[j];
- // 记录数量
- counts[remainder]++;
- }
- // 记录取的元素需要放的位置
- int index = 0;
- // 把数字取出来
- for (int k = 0; k < counts.length; k++) {
- // 记录数量的数组中当前余数记录的数量不为 0
- if (counts[k] != 0) {
- // 循环取出元素
- for (int l = 0; l < counts[k]; l++) {
- arr[index] = temp[k][l];
- // 记录下一个位置
- index++;
- }
- // 把数量置空
- counts[k] = 0;
- }
- }
- }
- }
- }