java算法;JAVA算法笔试题 收藏 0

Java常用的7大排序算法汇总

这段时间闲了下来，就抽了点时间总结了下java中常用的七大排序算法，希望以后可以回顾！

1.插入排序算法

插入排序的基本思想是在遍历数组的过程中，假设在序号 i 之前的元素即 [0..i-1] 都已经排好序，本趟需要找到 i 对应的元素 x 的正确位置 k ，并且在寻找这个位置 k 的过程中逐个将比较过的元素往后移一位，为元素 x “腾位置”，最后将 k 对应的元素值赋为 x ，一般情况下，插入排序的时间复杂度和空间复杂度分别为 O(n2 ) 和 O(1)。

1. /**

2. * @param int 未排序数组

3. * @return int 排完序数组

4. */

5. public int sortInsert(int[] array){

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

7. int temp = array[i];

8. int j;

9. for(j=i-1;j >= 0 && temp< array[j]; j–){

10. array[j + 1] = array[j];

11. }

12. array[j + 1] = temp;

13. }

14. return array;

15. }

2.选择排序算法

选择排序的基本思想是遍历数组的过程中，以 i 代表当前需要排序的序号，则需要在剩余的 [i…n-1] 中找出其中的最小值，然后将找到的最小值与 i 指向的值进行交换。因为每一趟确定元素的过程中都会有一个选择最大值的子流程，所以人们形象地称之为选择排序。选择排序的时间复杂度和空间复杂度分别为 O(n2 ) 和 O(1) 。

1. /**

2. * @param int 未排序数组

3. * @return int 排完序数组

4. */

5. public int sortSelect(int[] arr){

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

7. int miniPost = i;

8. for (int m = i + 1; m < arr.length; m++) {

9. if (arr[m] < arr[miniPost]) {

10. miniPost = m;

11. }

12. }

13. if (arr[i] > arr[miniPost]) {

14. int temp;

15. temp = arr[i];

16. arr[i] = arr[miniPost];

17. arr[miniPost] = temp;

18. }

19. }

20. return arr;

21. }

3.冒泡排序算法

冒泡排序是將比較大的數字沉在最下面，较小的浮在上面

1. /**

2. * @param int 未排序数组

3. * @return int 排完序数组

4. */

5. public int sortBubble(int[] array){

6. int temp;

7. // 第一层循环:表明比较的次数, 比如 length 个元素,比较次数为 length-1 次（肯定不需和自己比）

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

9. for (int j = array.length – 1; j > i; j–) {

10. if (array[j] < array[j – 1]) {

11. temp = array[j];

12. array[j] = array[j – 1];

13. array[j – 1] = temp;

14. }

15. }

16. }

17. return array;

18. }

4.快速排序算法

通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可以分别对这两部分记录继续进行排序,已达到整个序列有序的目的，本质就是,找一个基位(枢轴,分水岭,作用是左边的都比它小,右边的都比它大。

可随机,取名base，首先从序列最右边开始找比base小的,如果小,换位置,从而base移到刚才右边(比较时比base小)的位置(记为临时的high位),这样base右边的都比base大。然后,从序列的最左边开始找比base大的，如果大,换位置,从而base移动到刚才左边(比较时比base大)的位置(记为临时的low位),这样base左边的都比base小，循环以上两步,直到 low == heigh, 这使才真正的找到了枢轴,分水岭. 返回这个位置,分水岭左边和右边的序列,分别再来递归。

1. /**

2. * @param int 未排序数组

3. * @return int 排完序数组

4. */

5. public int sortQuick(int[] array){

6. return quickSort(array, 0, array.length-1);

7. }

8. private int quickSort(int[] arr, int low, int heigh) {

9. if (low < heigh) {

10. int division = partition(arr, low, heigh);

11. quickSort(arr, low, division – 1);

12. quickSort(arr, division + 1, heigh);

13. }

14. return arr;

15. }

16. // 分水岭,基位,左边的都比这个位置小,右边的都大

17. private int partition(int[] arr, int low, int heigh) {

18. int base = arr[low]; //用子表的第一个记录做枢轴(分水岭)记录

19. while (low < heigh) { //从表的两端交替向中间扫描

20. while (low < heigh && arr[heigh] >= base) {

21. heigh–;

22. }

23. // base 赋值给 当前 heigh 位,base 挪到(互换)到了这里,heigh位右边的都比base大

24. swap(arr, heigh, low);

25. while (low < heigh && arr[low] <= base) {

26. low++;

27. }

28. // 遇到左边比base值大的了,换位置

29. swap(arr, heigh, low);

30. }

31. // now low = heigh;

32. return low;

33. }

34. private void swap(int[] arr, int a, int b) {

35. int temp;

36. temp = arr[a];

37. arr[a] = arr[b];

38. arr[b] = temp;

39. }

5.合并排序算法

归并排序采用的是递归来实现，属于“分而治之”，将目标数组从中间一分为二，之后分别对这两个数组进行排序，排序完毕之后再将排好序的两个数组“归并”到一起，归并排序最重要的也就是这个“归并”的过程，归并的过程中需要额外的跟需要归并的两个数组长度一致的空间

1. /**

2. * @param int 未排序数组

3. * @return int 排完序数组

4. */

5. private int sort(int[] nums, int low, int high) {

6. int mid = (low + high) / 2;

7. if (low < high) {

8. // 左边

9. sort(nums, low, mid);

10. // 右边

11. sort(nums, mid + 1, high);

12. // 左右归并

13. merge(nums, low, mid, high);

14. }

15. return nums;

16. }

17. private void merge(int[] nums, int low, int mid, int high) {

18. int temp = new int[high – low + 1];

19. int i = low;// 左指针

20. int j = mid + 1;// 右指针

21. int k = 0;

22. // 把较小的数先移到新数组中

23. while (i <= mid && j <= high) {

24. if (nums[i] < nums[j]) {

25. temp[k++] = nums[i++];

26. } else {

27. temp[k++] = nums[j++];

28. }

29. }

30. // 把左边剩余的数移入数组

31. while (i <= mid) {

32. temp[k++] = nums[i++];

33. }

34. // 把右边边剩余的数移入数组

35. while (j <= high) {

36. temp[k++] = nums[j++];

37. }

38. // 把新数组中的数覆盖nums数组

39. for (int k2 = 0; k2 < temp.length; k2++) {

40. nums[k2 + low] = temp[k2];

41. }

42. }

43. public int sortMerge(int[] array) {

44. return sort(array, 0, array.length – 1);

45. }

6.希尔排序算法

希尔排序的诞生是由于插入排序在处理大规模数组的时候会遇到需要移动太多元素的问题。希尔排序的思想是将一个大的数组“分而治之”，划分为若干个小的数组。

以 gap 来划分，比如数组 [1, 2, 3, 4, 5, 6, 7, 8] ，如果以 gap = 2 来划分，可以分为 [1, 3, 5, 7] 和 [2, 4, 6, 8] 两个数组（对应的，如 gap = 3 ， 则划分的数组为： [1, 4, 7] 、 [2, 5, 8] 、 [3, 6] ）然后分别对划分出来的数组进行插入排序，待各个子数组排序完毕之后再减小 gap 值重复进行之前的步骤，直至 gap = 1 ，即对整个数组进行插入排序。

此时的数组已经基本上好序了，所以需要移动的元素会很小很小，解决了插入排序在处理大规模数组时较多移动次数的问题，希尔排序是插入排序的改进版，在数据量大的时候对效率的提升帮助很大，数据量小的时候建议直接使用插入排序就好了。

1. /**

2. * @param int 未排序数组

3. * @return int 排完序数组

4. */

5. public int sortShell(int[] array) {

6. // 取增量

7. int step = array.length / 2;

8. while (step >= 1) {

9. for (int i = step; i < array.length; i++) {

10. int temp = array[i];

11. int j = 0;

12. // 跟插入排序的区别就在这里

13. for (j = i – step; j >= 0 && temp < array[j]; j -= step) {

14. array[j + step] = array[j];

15. }

16. array[j + step] = temp;

17. }

18. step /= 2;

19. }

20. return array;

21. }

7.堆排序算法

本质就是先构造一个大顶堆,parent比children大,root节点就是最大的节点 把最大的节点(root)与尾节点(最后一个节点,比较小)位置互换，剩下最后的尾节点,现在最大,其余的,从第一个元素开始到尾节点前一位,构造大顶堆递归。

1. /**

2. * @param int 未排序数组

3. * @return int 排完序数组

4. */

5. public int sortHeap(int[] array) {

6. buildHeap(array);// 构建堆

7. int n = array.length;

8. int i = 0;

9. for (i = n – 1; i >= 1; i–) {

10. swap(array, 0, i);

11. heapify(array, 0, i);

12. }

13. return array;

14. }

15. private void buildHeap(int[] array) {

16. int n = array.length;// 数组中元素的个数

17. for (int i = n / 2 – 1; i >= 0; i–)

18. heapify(array, i, n);

19. }

20. private void heapify(int[] A, int idx, int max) {

21. int left = 2 * idx + 1;// 左孩子的下标（如果存在的话）

22. int right = 2 * idx + 2;// 左孩子的下标（如果存在的话）

23. int largest = 0;// 寻找3个节点中最大值节点的下标

24. if (left < max && A[left] > A[idx])

25. largest = left;

26. else

27. largest = idx;

28. if (right < max && A[right] > A[largest])

29. largest = right;

30. if (largest != idx) {

31. swap(A, largest, idx);

32. heapify(A, largest, max);

33. }

34. }

35. }

36. // 建堆函数，认为【s，m】中只有 s

37. // 对应的关键字未满足大顶堆定义，通过调整使【s，m】成为大顶堆=====================================================

38. public static void heapAdjust(int[] array, int s, int m) {

39. // 用0下标元素作为暂存单元

40. array[0] = array[s];

41. // 沿孩子较大的结点向下筛选

42. for (int j = 2 * s; j <= m; j *= 2) {

43. // 保证j为较大孩子结点的下标，j < m 保证 j+1 <= m ，不越界

44. if (j < m && array[j] < array[j + 1]) {

45. j++;

46. }

47. if (!(array[0] < array[j])) {

48. break;

49. }

50. // 若S位较小，应将较大孩子上移

51. array[s] = array[j];

52. // 较大孩子的值变成S位的较小值，可能引起顶堆的不平衡，故对其所在的堆进行筛选

53. s = j;

54. }

55. // 若S位较大，则值不变；否则，S位向下移动至2*s、4*s、。。。

56. array[s] = array[0];

内容来源：Android开发中文站

最新的TIOBE指数显示，Java编程已经超过了20%的普及门槛，这意味着每五行源代码当中就有一行采用Java编写。这不是Java语言有史以来最高分，它曾在多年前和C与C++语言竞争当中失去了头把交椅，但现在可能已经卷土重来。

java数据结构和算法-克鲁斯卡尔(Kruskal)算法

克鲁斯卡尔(Kruskal)算法，是用来求加权连通图的最小生成树的算法。

基本思想：按照权值从小到大的顺序选择n-1条边，并保证这n-1条边不构成回路。

具体做法：首先构造一个只含n个顶点的森林，然后依权值从小到大从连通网中选择边加入到森林中，并使森林中不产生回路，直至森林变成一棵树为止。

在含有n个顶点的连通图中选择n-1条边，构成一棵极小连通子图，并使该连通子图中n-1条边上权值之和达到最小，则称其为连通网的最小生成树。

• 对于如上图所示的连通网可以有多棵权值总和不相同的生成树。

某城市新增7个站点(A, B, C, D, E, F, G) ，现在需要修路把7个站点连通；各个站点的距离用边线表示(权) ，比如 A – B 距离 12公里。问：如何修路保证各个站点都能连通，并且总的修建公路总里程最短? （如下图）

• 以上图为例，来对克鲁斯卡尔进行演示(假设，用数组R保存最小生成树结果)。

第1步：将边<E,F>加入R中。 边<E,F>的权值最小，因此将它加入到最小生成树结果R中。

第2步：将边<C,D>加入R中。 上一步操作之后，边<C,D>的权值最小，因此将它加入到最小生成树结果R中。

第3步：将边<D,E>加入R中。 上一步操作之后，边<D,E>的权值最小，因此将它加入到最小生成树结果R中。

第4步：将边<B,F>加入R中。 上一步操作之后，边<C,E>的权值最小，但<C,E>会和已有的边构成回路；因此，跳过边<C,E>。同理，跳过边<C,F>。将边<B,F>加入到最小生成树结果R中。

第5步：将边<E,G>加入R中。上一步操作之后，边<E,G>的权值最小，因此将它加入到最小生成树结果R中。

第6步：将边<A,B>加入R中。 上一步操作之后，边<F,G>的权值最小，但<F,G>会和已有的边构成回路；因此，跳过边<F,G>。同理，跳过边<B,C>。将边<A,B>加入到最小生成树结果R中。

此时，最小生成树构造完成！它包括的边依次是：<E,F> <C,D> <D,E> <B,F> <E,G> <A,B>。

根据前面介绍的克鲁斯卡尔算法的基本思想和做法，我们能够了解到，克鲁斯卡尔算法重点需要解决的以下两个问题：

问题一：对图的所有边按照权值大小进行排序。

问题二 将边添加到最小生成树中时，怎么样判断是否形成了回路。

问题一很好解决，采用排序算法进行排序即可。

问题二，处理方式是：记录顶点在\”最小生成树\”中的终点，顶点的终点是\”在最小生成树中与它连通的最大顶点\”。然后每次需要将一条边添加到最小生存树时，判断该边的两个顶点的终点是否重合，重合的话则会构成回路。

在将<E,F> <C,D> <D,E>加入到最小生成树R中之后，这几条边的顶点就都有了终点：

1）、C的终点是F。

2）、D的终点是F。

3）、E的终点是F。

4）、F的终点是F。

关于终点的说明：

1）、就是将所有顶点按照从小到大的顺序排列好之后；某个顶点的终点就是\”与它连通的最大顶点\”。

2）、因此，接下来，虽然<C,E>是权值最小的边。但是C和E的终点都是F，即它们的终点相同，因此，将<C,E>加入最小生成树的话，会形成回路。这就是判断回路的方式。也就是说，我们加入的边的两个顶点不能都指向同一个终点，否则将构成回路。

package com.rf.data_structure_algorithm.algorithm.kruskal;

import java.util.Arrays;

/**

* @description: 克鲁斯卡尔算法

* @author: xiaozhi

* @create: 2020-11-16 20:55

*/

public class KruskalAlgorithm {

int edgeNum; //边的个数

char[] vertexs;//顶点数组

int[][] matrix; //邻接矩阵

static final int INF = Integer.MAX_VALUE;//使用 INF 表示两个顶点不能连通

//构造器

public KruskalAlgorithm(char[] vertexs, int[][] matrix) {

//初始化顶点, 复制拷贝的方式

this.vertexs = new char[vertexs.length];

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

this.vertexs[i] = vertexs[i];

}

//初始化边, 使用的是复制拷贝的方式

this.matrix = new int[vertexs.length][vertexs.length];

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

for (int j = 0; j < vertexs.length; j++) {

this.matrix[i][j] = matrix[i][j];

}

}

//统计边的条数

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

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

if (this.matrix[i][j] != INF) {//可以连通，边的个数+1

edgeNum++;

}

}

}

}

/**

* @Description: 打印邻接矩阵

* @Author: xz

* @Date: 2020/11/16 21:11

*/

public void print() {

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

for (int j = 0; j < vertexs.length; j++) {

System.out.printf(\”%12d\”, matrix[i][j]);

}

System.out.println();//换行

}

}

/**

* @Description: 对边进行排序（冒泡排序）

* @Param: edges 边的集合

* @Author: xz

* @Date: 2020/11/16 21:28

*/

public void sortEdges(KData[] edges){

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

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

if(edges[j].weight >edges[j+1].weight){

KData temp =edges[j];

edges[j]=edges[j+1];

edges[j+1]=temp;

}

}

}

}

/**

* @Description:

* @Param: c 表示顶点的值，比如‘A’，‘B’…

* @Author: xz

* @return: 返回c 顶点的下标，如果找不到返回-1

* @Date: 2020/11/16 21:35

*/

public int getPosition(char c){

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

if(vertexs[i] ==c){

return i;

}

}

//找不到返回-1

return -1;

}

/**

* @Description: 获取图中的边放到KData[] 数组中，通过 matrix 邻接矩阵获取

* KData[] 的形式如: [[<A, B>= 12], [<A, F>= 16],…]

* @Author: xz

* @Date: 2020/11/16 21:41

*/

public KData[] getEdges(){

int index=0;

KData[] edges=new KData[edgeNum];

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

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

if(matrix[i][j] != INF){

edges[index++] =new KData(vertexs[i],vertexs[j],matrix[i][j]);

}

}

}

return edges;

}

/**

* 功能: 获取下标为i的顶点的终点(), 用于后面判断两个顶点的终点是否相同

* @param ends ： 数组就是记录了各个顶点对应的终点是哪个,ends 数组是在遍历过程中，逐步形成

* @param i : 表示传入的顶点对应的下标

* @Author: xz

* @return 返回的就是 下标为i的这个顶点对应的终点的下标

* @Date: 2020/11/16 21:49

*/

private int getEnd(int[] ends, int i) {

while(ends[i] != 0) {

i = ends[i];

}

return i;

}

/**

* @Description: 克鲁斯卡尔方法

* @Author: xz

* @Date: 2020/11/16 21:52

*/

public void kruskal() {

int index = 0; //表示最后结果数组的索引

int[] ends = new int[edgeNum]; //用于保存\”已有最小生成树\” 中的每个顶点在最小生成树中的终点

//创建结果数组, 保存最后的最小生成树

KData[] rets = new KData[edgeNum];

//获取图中 所有的边的集合 ， 一共有12边

KData[] edges = getEdges();

System.out.println(\”图的边的集合=\” + Arrays.toString(edges) + \” 共\”+ edges.length); //12

//按照边的权值大小进行排序(从小到大)

sortEdges(edges);

//遍历edges 数组，将边添加到最小生成树中时，判断是准备加入的边否形成了回路，如果没有，就加入 rets, 否则不能加入

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

//获取到第i条边的第一个顶点(起点)

int p1 = getPosition(edges[i].start); //p1=4

//获取到第i条边的第2个顶点

int p2 = getPosition(edges[i].end); //p2 = 5

//获取p1这个顶点在已有最小生成树中的终点

int m = getEnd(ends, p1); //m = 4

//获取p2这个顶点在已有最小生成树中的终点

int n = getEnd(ends, p2); // n = 5

//是否构成回路

if(m != n) { //没有构成回路

ends[m] = n; // 设置m 在\”已有最小生成树\”中的终点 <E,F> [0,0,0,0,5,0,0,0,0,0,0,0]

rets[index++] = edges[i]; //有一条边加入到rets数组

}

}

//<E,F> <C,D> <D,E> <B,F> <E,G> <A,B>。

//统计并打印 \”最小生成树\”, 输出 rets

System.out.println(\”最小生成树为=================\”);

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

System.out.println(rets[i]);

}

}

/**

* @Description: 测试方法

* @Author: xz

* @Date: 2020/11/16 21:15

*/

public static void main(String[] args) {

//定义7个顶点

char[] vertexs = {\’A\’, \’B\’, \’C\’, \’D\’, \’E\’, \’F\’, \’G\’};

//定义克鲁斯卡尔算法的邻接矩阵 INF:表示两个顶点不能连通，0：表示顶点自己和顶点自己相连

int matrix[][] = {

/*A*//*B*//*C*//*D*//*E*//*F*//*G*/

/*A*/ {0, 12, INF, INF, INF, 16, 14},

/*B*/ {12, 0, 10, INF, INF, 7, INF},

/*C*/ {INF, 10, 0, 3, 5, 6, INF},

/*D*/ {INF, INF, 3, 0, 4, INF, INF},

/*E*/ {INF, INF, 5, 4, 0, 2, 8},

/*F*/ {16, 7, 6, INF, 2, 0, 9},

/*G*/ {14, INF, INF, INF, 8, 9, 0}

};

//创建KruskalAlgorithm 对象实例

KruskalAlgorithm kruskalAlgorithm = new KruskalAlgorithm(vertexs, matrix);

//输出构建的邻接矩阵

System.out.println(\”邻接矩阵============== \\n\”);

kruskalAlgorithm.print();

System.out.println();

System.out.println(\”图中的边及权值————————-\”);

KData[] edges = kruskalAlgorithm.getEdges();

System.out.println(\”排序前=\”+Arrays.toString(edges));

kruskalAlgorithm.sortEdges(edges);

System.out.println(\”排序后=\”+Arrays.toString(edges));

System.out.println();

kruskalAlgorithm.kruskal();

}

}

/**

* @Description: 创建一个类KData，它的对象实例就表示一条边

* @Author: xz

* @Date: 2020/11/16 21:22

*/

class KData {

char start; //边的一个点

char end; //边的另外一个点

int weight; //边的权值

//构造器

public KData(char start, char end, int weight) {

this.start = start;

this.end = end;

this.weight = weight;

}

//重写toString, 便于输出边信息

@Override

public String toString() {

return \”KData [<\” + start + \”, \” + end + \”>= \” + weight + \”]\”;

}

}

运行：

私信666领取资料

本文作者及来源:Renderbus瑞云渲染农场https://www.renderbus.com