算法

解决算法问题提升算法能力：->算法竞赛和题解网站 #生活技巧# #学习技巧# #编程学习指南#

目录

术语：

选择排序

插入排序

冒泡排序

希尔排序

归并排序

快速排序

术语：

1、稳定排序：如果 a 原本在 b 的前面，且 a == b，排序之后 a 仍然在 b 的前面，则为稳定排序。

2、非稳定排序：如果 a 原本在 b 的前面，且 a == b，排序之后 a 可能不在 b 的前面，则为非稳定排序。

3、原地排序：原地排序就是指在排序过程中不申请多余的存储空间，只利用原来存储待排数据的存储空间进行比较和交换的数据排序。

4、非原地排序：需要利用额外的数组来辅助排序。

5、时间复杂度：一个算法需要执行的次数，常见的时间复杂度（常数阶O(1),对数阶O(log2 n),线性阶O(n),线性对数阶O(n log2 n),k次方阶O(n^K),指数阶O(2^n)）。

6、空间复杂度：运行完一个算法所需的内存大小。

选择排序

定义：首先，找到数组中最小的那个元素，其次，将它和数组的第一个元素交换位置(如果第一个元素就是最小元素那么它就和自己交换)。其次，在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序。

特点：非稳定排序，原地排序，时间复杂度O(n^2)，空间复杂度O(1)

package com.anran.example.order;

import java.util.Scanner;

public class SelectSort {

/**

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

String[] nums = sc.nextLine().split(" ");

for (int i = 0; i <nums.length - 1; i ++) {

// 记录最小值的下标

int min = i;

for (int j = i + 1; j < nums.length; j++) {

if (Integer.parseInt(nums[j]) < Integer.parseInt(nums[min])) {

min = j;

}

}

String minNum = nums[min];

nums[min] = nums[i];

nums[i] = minNum;

}

for (String str : nums) {

System.out.print (str + " ");

}

}

}

插入排序

定义：从第二个元素进行操作，分别对当前元素左侧的进行对比，找到比自己小的元素时标记位置，然后将标记位置之后到自己位置的数据依次往后移动一位，最后将自身插入到标记元素的后面，从而保证自身开始之前的是有序。

特点：稳定排序，原地排序，时间复杂度（O(n^2)），空间复杂度O(1)

package com.anran.example.order;

import java.util.Scanner;

public class InsertSort {

/**

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

String[] nums = sc.nextLine().split(" ");

for (int i = 1; i <nums.length; i++) {

// 在前面排好序的序列中找第一个比自己小的数字位置

int site = i - 1;

while (site >= 0 && Integer.parseInt(nums[site]) >= Integer.parseInt(nums[i])){

site--;

}

// 将自己插入到找好的位置，中间有序的信息依次往后移动一位

String str = nums[i];

for (int j = i; j > site + 1; j--) {

nums[j] = nums[j - 1];

}

nums[site + 1] = str;

}

for (String str : nums) {

System.out.print (str + " ");

}

}

}

冒泡排序

定义：相邻两个元素逐个对比，将相对较大的元素移动到末尾

特点：稳定排序，原地排序，时间复杂度（O(n^2)），空间复杂度O(1)

package com.anran.example.order;

import java.util.Scanner;

public class BubbleSort {

/**

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

String[] nums = sc.nextLine().split(" ");

for (int i = 0; i <nums.length; i++) {

for(int j = 0; j < nums.length - i - 1; j++) {

if (Integer.parseInt(nums[j]) > Integer.parseInt(nums[j + 1])) {

String str = nums[j];

nums[j] = nums[j + 1];

nums[j + 1] = str;

}

}

}

for (String str : nums) {

System.out.print (str + " ");

}

}

}

希尔排序

定义：希尔排序的思想是采用插入排序的方法，先让数组中任意间隔为 h 的元素有序，刚开始 h 的大小可以是 h = n / 2,接着让 h = n / 4，让 h 一直缩小，当 h = 1 时，也就是此时数组中任意间隔为1的元素有序，此时的数组就是有序的了。

特点：非稳定排序，原地排序，时间复杂度（O(nlogn)），空间复杂度（O(1)）

package com.anran.example.order;

import com.fasterxml.jackson.core.JsonProcessingException;

import com.fasterxml.jackson.databind.ObjectMapper;

import java.util.Scanner;

public class ShellSort {

/**

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

String[] nums = sc.nextLine().split(" ");

// 分组力度

for (int gap = nums.length / 2; gap > 0; gap = gap / 2) {

System.out.println(gap);

// 对各个分组的数据进行插入排序

insertSort(nums, gap);

try {

System.out.println(new ObjectMapper().writeValueAsString(nums));

} catch (JsonProcessingException e) {

e.printStackTrace();

}

}

for (String str : nums) {

System.out.print (str + " ");

}

}

private static void insertSort(String[] nums, int gap) {

for (int i = gap; i < nums.length; i++) {

int site = i - gap;

// 在前面排好序的序列中找第一个比自己小的数字位置

while (site >= 0 && Integer.parseInt(nums[site]) >= Integer.parseInt(nums[i])) {

site = site - gap;

}

String str = nums[i];

// 将自己插入到找好的位置，中间有序的信息依次往后移动gap位

for (int j = i; j > site + gap; j = j - gap) {

nums[j] = nums[j - gap];

}

nums[site + gap] = str;

}

}

}

输出：

归并排序

定义：通过递归的方式将大的数组一直分割，直到数组的大小为 1，此时只有一个元素，那么该数组就是有序的了，之后再把两个数组大小为1的合并成一个大小为2的，再把两个大小为2的合并成4的 ….. 直到全部小的数组合并起来。

特点：稳定排序，非原地排序，时间复杂度（O(nlogn)），空间复杂度（O(n) ）

package com.anran.example.order;

import java.util.Scanner;

public class MergeSort {

/**

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

String[] nums = sc.nextLine().split(" ");

sort(nums, 0 , nums.length - 1);

for (String str : nums) {

System.out.print (str + " ");

}

}

private static void sort(String[] nums, int left,int right) {

// 递归调用结束判断

if (left < right) {

// 获取中位数

int mid = (left + right) / 2;

// 左侧进行排序

sort(nums, left, mid);

// 右侧进行排序

sort(nums, mid + 1, right);

//合并左右侧的数据

merge(nums, left, mid, right);

}

}

private static void merge(String[] nums, int left, int mid, int right) {

// 临时数据保存

String[] temNums = new String[right - left + 1];

int leftStart = left;

int rightStart = mid + 1;

int newArrayStart = 0;

// 分别对左右两个数组中的数据进行对比排序

while (leftStart <= mid && rightStart <= right) {

if (Integer.parseInt(nums[leftStart]) > Integer.parseInt(nums[rightStart])) {

temNums[newArrayStart++] = nums[rightStart++];

} else {

temNums[newArrayStart++] = nums[leftStart++];

}

}

// 处理其中某一个么有添加进行的数据

while (leftStart <= mid) {

temNums[newArrayStart++] = nums[leftStart++];

}

while (rightStart <= right) {

temNums[newArrayStart++] = nums[rightStart++];

}

// 把临时数组中的数据复制到原始数据中

for (int i = 0; i < newArrayStart; i++) {

nums[left++] = temNums[i];

}

}

}

快速排序

定义：我们从数组中选择一个元素，我们把这个元素称之为中轴元素吧，然后把数组中所有小于中轴元素的元素放在其左边，所有大于或等于中轴元素的元素放在其右边，显然，此时中轴元素所处的位置的是有序的。也就是说，我们无需再移动中轴元素的位置。

从中轴元素那里开始把大的数组切割成两个小的数组(两个数组都不包含中轴元素)，接着我们通过递归的方式，让中轴元素左边的数组和右边的数组也重复同样的操作，直到数组的大小为1，此时每个元素都处于有序的位置。

特点：非稳定排序，原地排序，时间复杂度（O(nlogn)），空间复杂度：O(1)

package com.anran.example.order;

import java.util.Scanner;

public class QuickSort {

/**

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

String[] nums = sc.nextLine().split(" ");

sort(nums, 0, nums.length - 1);

for (String str : nums) {

System.out.print (str + " ");

}

}

private static void sort(String[] nums, int left, int right) {

// 递归结束条件

if (left < right) {

// 获取中位数所在的位置

int mid = getMidSite(nums, left, right);

// 处理中位数左侧

sort(nums, left, mid - 1);

// 处理中位数右侧

sort(nums, mid + 1, right);

}

}

private static int getMidSite(String[] nums, int left, int right) {

// 选取当前数据中的第一个作为中轴元素

int midVaule = Integer.parseInt(nums[left]);

int leftStart = left;

int rightStart = right;

// 将现有元素和中轴元素进行对比进行简单排序

while (true) {

// 从左侧获取第一个大于中轴元素的位置,小于的不关心

while (leftStart <= rightStart && Integer.parseInt(nums[leftStart]) <= midVaule) {

leftStart++;

}

// 从右侧获取第一个小于中轴元素的位置，大于的不关心

while (leftStart <= rightStart && Integer.parseInt(nums[rightStart]) >= midVaule) {

rightStart--;

}

if (leftStart >= rightStart) {

// 此时已经按照中位数进行了排序，中位数最后替换的位置是rightStart

break;

}

// 如果没有结束，需要将发现的数据进行交换

String str = nums[leftStart];

nums[leftStart] = nums[rightStart];

nums[rightStart] = str;

}

// 将中位数回填到最后一次判断的位置

nums[left] = nums[rightStart];

nums[rightStart] = String.valueOf(midVaule);

return rightStart;

}

}

传送门：https://www.cnblogs.com/itsharehome/p/11058010.html

网址：算法 https://www.yuejiaxmz.com/news/view/115049

相关内容

算法在身边——学习算法从妈妈的菜谱开始
九大智能优化算法复习（2）：遗传算法
算法人生（15）：从“智能任务调度算法”到“15
社交算法
离散化算法
计算机维护方法
什么是类比估算法=自上而下的估算
pe值算法=公式技巧.doc
揭秘原始速算法：轻松提高计算效率，告别繁琐运算的神奇技巧大公开！
APS智能排产+运筹优化算法=？

随便看看