- 算法思想: 首先在一个已经排好序的序列当中，我们要插入的新的值依次与原先序列中的值进行比较，（以升序为例）将要插入的值插入到序列当中使得该值前面的数都小于它，后面的数都大于它，从而得到的新序列依然是有序的
- 时间复杂度最好 O(n) 最差 O(n平方)
- 空间复杂度 O(1)
public class InsertSort {
public static void main(String[] args) {
// 插入排序
int[] arr = {1, 2, 4, 6, 8, 5, 3};
for(int i = 1; i < arr.length; i++){
for(int j = i; j > 0; j--){
if(arr[j] < arr[j - 1]){
int temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
} else {
break;
}
}
}
for(int i = 0; i < arr.length; i++){
System.out.println(arr[i]);
}
}
}
- 算法思想: 如果有N个元素需要排序，那么首先从N个元素中找到最小的那个元素与第0位置上的元素交换（说明一点，如果没有比原本在第0位置上的元素小的就不用交换了，后面的同样是），然后再从剩下的N-1个元素中找到最小的元素与第1位置上的元素交换，之后再从剩下的N-2个元素中找到最小的元素与第2位置上的元素交换，.......直到所有元素都排序好（也就是直到从剩下的2个元素中找到最小的元素与第N-2位置上的元素交换）
- 时间复杂度 O(n平方)
- 空间复杂度 O(1)
public class SelectSort{
public static void main(String[] args) {
// 选择排序
int[] arr = {1, 2, 4, 6, 8, 5, 3};
for(int i = 0; i < arr.length - 1; i++){
int min = i;
for(int j = i + 1; j < arr.length; j++){
if(arr[min] > arr[j]){
min = j;
}
}
if(min != i){
int temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
}
}
for(int i = 0; i < arr.length; i++){
System.out.println(arr[i]);
}
}
}
- 算法思想: 将n个元素分成个含n/2个元素的子序列。用合并排序法对两个子序列递归的排序。合并两个已排序的子序列已得到排序结果
- 时间复杂度: O(nlogn)
- 空间复杂度: O(n)
// 迭代版本
public static void merge_sort(int[] arr) {
int len = arr.length;
int[] result = new int[len];
int block, start;
// 原版代码的迭代次数少了一次，没有考虑到奇数列数组的情况
for (block = 1; block < len * 2; block *= 2) {
for (start = 0; start < len; start += 2 * block) {
int low = start;
int mid = Math.min((start + block), len);
int high = Math.min((start + 2 * block), len);
//两个块的起始下标及结束下标
int start1 = low;
int start2 = mid;
//开始对两个block进行归并排序
while (start1 < mid && start2 < high) {
result[low++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
}
while (start1 < mid) {
result[low++] = arr[start1++];
}
while (start2 < high) {
result[low++] = arr[start2++];
}
}
int[] temp = arr;
arr = result;
result = temp;
}
result = arr;
}
// 递归版本
public static void mergeSortRecursive(int[] arr, int[] result, int start, int end) {
if (start >= end) {
return;
}
int len = end - start;
int mid = len / 2 + start;
int start1 = start;
int start2 = mid + 1;
mergeSortRecursive(arr, result, start1, mid);
mergeSortRecursive(arr, result, start2, end);
int k = start;
while (start1 <= mid && start2 <= end) {
result[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
}
while (start1 <= mid) {
result[k++] = arr[start1++];
}
while (start2 <= end) {
result[k++] = arr[start2++];
}
for (k = start; k <= end; k++) {
arr[k] = result[k];
}
}
public static void mergeSort(int[] arr) {
int len = arr.length;
int[] result = new int[len];
mergeSortRecursive(arr, result, 0, len - 1);
}
- 算法思想: 待排序序列构造成一个大顶堆，此时整个序列的最大值就是堆顶的根节点，将其与末尾元素进行交换，此时末尾元素就为最大值， 然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了
- 时间复杂度: O(nlogn)
- 空间复杂度: O(1)
public class Demo {
public static void main(String[] args) {
int[] arr = {1, 2, 5, 4, 3, 7};
heapSort(arr);
for(int i = 0; i < arr.length; i++){
System.out.println(arr[i]);
}
}
public static void heapSort(int[] arr){
// 构造大顶堆
for(int i = arr.length / 2 - 1; i >=0; i--){
adjustHeap(arr, i, arr.length);
}
for(int j = arr.length - 1; j > 0; j--){
swap(arr, 0, j);
adjustHeap(arr, 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 i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
- 算法思想: 在待排序列中，按照某种方式挑出一个元素，作为 "基准"（pivot），以该基准在序列中的实际位置，把序列分成两个子序列。此时，在基准左边的元素都比该基准小，在基准右边的元素都比基准大，递归地对两个序列进行快速排序，直到序列为空或者只有一个元素。
- 时间复杂度: O(nlogn)
- 空间复杂度: O(1)
// 快速排序算法
public class QuickSort {
public static void main(String[] args) {
int[] arr = {5, 6, 7, 8, 9, 1, 2, 4, 3};
int low = 0;
int high = arr.length - 1;
quickSort(arr, low, high);
for(int i = 0; i < arr.length; i++){
System.out.println(arr[i]);
}
}
public static void quickSort(int[] arr, int low, int high){
if(low < high){
int middle = partition(arr, low, high);
quickSort(arr, low, middle - 1);
quickSort(arr, middle + 1, high);
}
}
public static int partition(int[] arr, int low, int high){
int i = low;
int j = high;
int x = arr[low];
while(i < j){
while(arr[j] > x && i < j){
j--;
}
if(i < j){
arr[i] = arr[j];
i++;
}
while(arr[i] < x && i < j){
i++;
}
if(i < j){
arr[j] = arr[i];
j--;
}
}
arr[i] = x;
return i;
}
}
- 算法思想: 从前往后（或从后往前）两两比较相邻元素的值，若为逆序（即A[I-1]>A[I]）,则交换它们，直到序列比较完。我们称它为第一趟冒泡，结果是将最小的元素交换到待排序列的第一个位置（或将最大的元素交换到待排序列的最后一个位置），关键字最小的元素如气泡一样逐渐向上“漂浮”。最终一个一个排好了位置。
- 时间复杂度: O( n^2 )
- 空间复杂度: O(1)
public class BubbleSort {
public static void main(String[] args) {
// 冒泡排序
int[] arr = {2, 1, 4, 6, 8, 5, 3};
for(int i = 0; i < arr.length; i++){
for(int j = 0; j < arr.length - i - 1; j++){
if(arr[j + 1] < arr[j]){
int temp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = temp;
}
}
}
for(int i = 0; i < arr.length; i++){
System.out.println(arr[i]);
}
}
}
- 算法思想: 采用插入排序的方法，先让数组中任意间隔为 gap 的元素有序，刚开始 gap 的大小可以是 gap = n / 2,接着让 gap = (n / 2) / 2，让 h 一直缩小，当 gap = 1 时，也就是此时数组中任意间隔为1的元素有序，此时的数组就是有序的了。
- 时间复杂度: O(N)
- 空间复杂度: O(1)
public class ShellSort {
public static void main(String[] args) {
// 希尔排序, 插入排序的一种
int[] arr = {5, 1, 7, 3, 1, 6, 9, 4};
for (int step = arr.length / 2; step > 0; step /= 2) {
for(int i = step; i < arr.length; i++){
int j = i;
int temp = arr[j];
while(j - step >= 0 && arr[j - step] > temp){
arr[j] = arr[j - step];
j = j - step;
}
arr[j] = temp;
}
}
for(int i = 0; i < arr.length; i++){
System.out.println(arr[i]);
}
}
}
- 第一步：找出原数组中元素值最大的，记为max。
- 第二步：创建一个新数组count，其长度是max加1，其元素默认值都为0。
- 第三步：遍历原数组中的元素，以原数组中的元素作为count数组的索引，以原数组中的元素出现次数作为count数组的元素值。
- 第四步：创建结果数组result，起始索引index。
- 第五步：遍历count数组，找出其中元素值大于0的元素，将其对应的索引作为元素值填充到result数组中去，每处理一次，count中的该元素值减1，直到该元素值不大于0，依次处理count中剩下的元素。
- 第六步：返回结果数组result。
public class CountingSort {
public static void main(String[] args) {
// 桶排序, 插入排序的一种
int[] arr = {5, 1, 7, 3, 1, 6, 9, 4};
int maxValue = 9;
int minValue = 1;
// 最大值减去最小值 加1
int[] res = new int[maxValue - minValue + 1];
for(int i = 0; i < arr.length; i++){
res[arr[i] - minValue]++;
}
for(int i = 0; i < res.length; i++){
if(res[i] != 0){
for(int j = 0; j < res[i]; j++){
System.out.println(i + minValue);
}
}
}
}
}
- 算法思想: 把待排序的数尽量均匀地放到各个桶中，再对各个桶进行局部的排序，最后再按序将各个桶中的数输出，即可得到排好序的数。首先确定桶的个数。因为桶排序最好是将数据均匀地分散在各个桶中，那么桶的个数最好是应该根据数据的分散情况来确定。首先找出所有数据中的最大值mx和最小值mn；根据mx和mn确定每个桶所装的数据的范围 size，有size = (mx - mn) / n + 1，n为数据的个数，需要保证至少有一个桶，故而需要加个1；求得了size即知道了每个桶所装数据的范围，还需要计算出所需的桶的个数cnt，有cnt = (mx - mn) / size + 1，需要保证每个桶至少要能装1个数，故而需要加个1；求得了size和cnt后，即可知第一个桶装的数据范围为 [mn, mn + size)，第二个桶为 [mn + size, mn + 2 * size)，…，以此类推因此步骤2中需要再扫描一遍数组，将待排序的各个数放进对应的桶中。对各个桶中的数据进行排序，可以使用其他的排序算法排序，例如快速排序；也可以递归使用桶排序进行排序；将各个桶中排好序的数据依次输出，最后得到的数据即为最终有序。
- 时间复杂度: O(n)
- 空间复杂度: O(n)
public class BucketSort {
public static void sort(int[] num) {
// 找最大值和最小值
int max = Integer.MIN_VALUE , min = Integer.MAX_VALUE;
for (int i = 0; i < num.length; i++) {
if (num[i] > max) {
max = num[i];
}
if (num[i] < min) {
min = num[i];
}
}
// 桶数
int bucketNum = (max - min) / num.length + 1;
List<ArrayList<Integer>> bucketArray = new ArrayList<>(bucketNum);
for (int i = 0; i < bucketNum; i++) {
bucketArray.add(new ArrayList<Integer>());
}
// 将每个元素放入桶，通过值计算这个元素分在哪个桶
int index;
for (int i = 0; i < num.length; i++) {
index = (num[i] - min) / num.length;
bucketArray.get(index).add(num[i]);
}
// 对每个桶排序
for (int i = 0; i < bucketArray.size(); i++) {
Collections.sort(bucketArray.get(i));
}
// 加入原数组
index = 0;
for (ArrayList<Integer> integers : bucketArray) {
for (int j = 0; j < integers.size(); j++) {
num[index++] = integers.get(j);
}
}
}
public static void main(String[] args) {
int[] num = {4,1,7,9,2,5,2,3,2};
BucketSort.sort(num);
for (int i = 0; i < num.length; i++) {
System.out.print(num[i] + " ");
}
}
}
- 算法思想: 将所有待比较数值 统一为同样的数位长度，数位较短的数 前面补零。然后从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，序列就变成了一个有序序列
- 时间复杂度: O(n)
- 空间复杂度: O(n)
public void radixSort(int[] arr) {
// 1. 得到数组中的最大值，并获取到该值的位数。用于循环几轮
int max = arr[0];
for (int i = 0; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
// 得到位数
int maxLength = (max + "").length();
// 定义桶 和 标识桶中元素个数
int[][] bucket = new int[10][arr.length];
int[] bucketCounts = new int[bucket.length];
// 总共需要进行 maxLength 轮
for (int k = 1, n = 1; k <= maxLength; k++, n *= 10) {
// 进行桶排序
for (int i = 0; i < arr.length; i++) {
// 获取该轮的桶索引：每一轮按 10 的倍数递增，获取到对应数位数
// 这里额外使用一个步长为 10 的变量 n 来得到每一次递增后的值
int bucketIndex = arr[i] / n % 10;
// 放入该桶中
bucket[bucketIndex][bucketCounts[bucketIndex]] = arr[i];
// 标识该桶元素多了一个
bucketCounts[bucketIndex]++;
}
// 将桶中元素获取出来，放到原数组中
int index = 0;
for (int i = 0; i < bucket.length; i++) {
if (bucketCounts[i] == 0) {
// 该桶无有效元素，跳过不获取
continue;
}
// 获取桶中有效的个数
for (int j = 0; j < bucketCounts[i]; j++) {
arr[index++] = bucket[i][j];
}
// 取完后，重置该桶的元素个数为 0 ，下一次才不会错乱数据
bucketCounts[i] = 0;
}
System.out.println("第" + k + "轮排序后：" + Arrays.toString(arr));
}
}
本文暂时没有评论，来添加一个吧(●'◡'●)