MasterYangBlog
首页
时间轴
标签
分类
友链
留言板
关于
avatar
文章
72
标签
51
分类
27
首页
时间轴
标签
分类
友链
留言板
关于
目录
  1. 1. 冒泡排序
  2. 2. 快速排序
  3. 3. 归并排序
  4. 4. 二分查找
  5. 5. 二叉树相关
常用排序算法总结
|算法与数据结构
阅读量:

冒泡排序

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
 * 冒泡排序 时间复杂度 O(n^2) 空间复杂度O(1)
 */
public class BubbleSort {

   public static void bubbleSort(int[] data) {

      System.out.println("开始排序");
      int arrayLength = data.length;

      for (int i = 0; i < arrayLength - 1; i++) {

         boolean flag = false;

         for (int j = 0; j < arrayLength - 1 - i; j++) {
            if(data[j] > data[j + 1]){
               int temp = data[j + 1];
               data[j + 1] = data[j];
               data[j] = temp;
               flag = true;
            }
         }

         System.out.println(java.util.Arrays.toString(data));

         if (!flag)
            break;
      }
   }

   public static void main(String[] args) {

      int[] data = { 9, -16, 21, 23, -30, -49, 21, 30, 30 };

      System.out.println("排序之前：\n" + java.util.Arrays.toString(data));

      bubbleSort(data);

      System.out.println("排序之后：\n" + java.util.Arrays.toString(data));
   }
}

快速排序

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
package com.ys.shuzu;

/**
 * 标准快排
 * 【注意】
 * 最左边为基准数（flag）的时候，从右开始往前遍历。
 */
public class Kuaisupaixu {
    public static void quicksort(int[] arr, int left, int right) {
        if (left > right) {
            return;
        }
        int flag = arr[left];
        int l = left;
        int r = right;
        int temp;

        while (l != r) {
            while (arr[r] >= flag && l < r) { //【重点】
                r -= 1;
            }
            while (arr[l] <= flag && l < r) {
                l += 1;
            }
            temp = arr[r];
            arr[r] = arr[l];
            arr[l] = temp;

        }
        arr[left] = arr[l];
        arr[l] = flag;

        quicksort(arr, left, l - 1);
        quicksort(arr, l + 1, right);
    }

    public static void main(String[] args) {
        int[] a = {9, 2, 1, 5, 4, 8, 7, 6, 1, 0};
        quicksort(a, 0, a.length - 1);
        for (int i : a) {
            System.out.print(i + " ");
        }
    }
}
scala
1
2
3
4
5
6
7
8
9
10
11
12
/**
 * 快排
 * 时间复杂度:平均时间复杂度为O(nlogn)
 * 空间复杂度:O(logn)，因为递归栈空间的使用问题
 */
def quickSort(list: List[Int]): List[Int] = list match {
    case Nil => Nil
    case List() => List()
    case head :: tail =>
      val (left, right) = tail.partition(_ < head)
      quickSort(left) ::: head :: quickSort(right)
  }

归并排序

核心思想：不断的将大的数组分成两个小数组，直到不能拆分为止，即形成了单个值。此时使用合并的排序思想对已经有序的数组进行合并，合并为一个大的数据，不断重复此过程，直到最终所有数据合并到一个数组为止。

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
package com.ys.shuzu;

import java.util.Arrays;

/**
 * 【归并排序】
 * 时间复杂度nlogn（平均，最好，最坏都是这个值）
 * 空间复杂度n（用空间换时间，时间上和快排差不多）
 */
public class MergeSort {

    public static void main(String[] args) {
        int arr[] = {8, 4, 5, 7, 1, 3, 6, 2}; //

        int temp[] = new int[arr.length]; //归并排序需要一个额外空间
        mergeSort(arr, 0, arr.length - 1, temp);

        System.out.println("归并排序后=" + Arrays.toString(arr));
    }

    //分+合方法
    public static void mergeSort(int[] arr, int left, int right, int[] temp) {
        if (left < right) {
            int mid = (left + right) / 2; //中间索引
            //向左递归进行分解
            mergeSort(arr, left, mid, temp);
            //向右递归进行分解
            mergeSort(arr, mid + 1, right, temp);
            //合并
            merge(arr, left, mid, right, temp);
        }
    }
    //合并的方法

    /**
     * @param arr   排序的原始数组
     * @param left  左边有序序列的初始索引
     * @param mid   中间索引
     * @param right 右边索引
     * @param temp  做中转的数组
     */
    public static void merge(int[] arr, int left, int mid, int right, int[] temp) {

        int i = left; // 初始化i, 左边有序序列的初始索引
        int j = mid + 1; //初始化j, 右边有序序列的初始索引
        int t = 0; // 指向temp数组的当前索引

        //(一)
        //先把左右两边(有序)的数据按照规则填充到temp数组
        //直到左右两边的有序序列，有一边处理完毕为止
        while (i <= mid && j <= right) {//继续
            //如果左边的有序序列的当前元素，小于等于右边有序序列的当前元素
            //即将左边的当前元素，填充到 temp数组
            //然后 t++, i++
            if (arr[i] <= arr[j]) {
                temp[t] = arr[i];
                t += 1;
                i += 1;
            } else { //反之,将右边有序序列的当前元素，填充到temp数组
                temp[t] = arr[j];
                t += 1;
                j += 1;
            }
        }

        //(二)
        //把有剩余数据的一边的数据依次全部填充到temp
        while (i <= mid) { //左边的有序序列还有剩余的元素，就全部填充到temp
            temp[t] = arr[i];
            t += 1;
            i += 1;
        }

        while (j <= right) { //右边的有序序列还有剩余的元素，就全部填充到temp
            temp[t] = arr[j];
            t += 1;
            j += 1;
        }

        //(三)
        //将temp数组的元素拷贝到arr
        //注意，并不是每次都拷贝所有
        t = 0;
        int tempLeft = left; //
        //第一次合并 tempLeft = 0 , right = 1 //  tempLeft = 2  right = 3 // tL=0 ri=3
        //最后一次 tempLeft = 0  right = 7
        while (tempLeft <= right) {
            arr[tempLeft] = temp[t];
            t += 1;
            tempLeft += 1;
        }
    }
}
scala
1
2
3
4
5
6
7
8
9
10
11
12
/**
 * 快排 
 * 时间复杂度:O(nlogn)
 * 空间复杂度:O(n)
 */
def merge(left: List[Int], right: List[Int]): List[Int] = (left, right) match {
    case (Nil, _) => right
    case (_, Nil) => left
    case (x :: xTail, y :: yTail) =>
      if (x <= y) x :: merge(xTail, right)
      else y :: merge(left, yTail)
  }

二分查找

scala
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * 二分查找 时间复杂度O(log2n);空间复杂度O(1)
 */
 
def binarySearch(arr:Array[Int],left:Int,right:Int,findVal:Int): Int={
  if(left>right){//递归退出条件，找不到，返回-1
    -1
  }

  val midIndex = (left+right)/2

  if (findVal < arr(midIndex)){//向左递归查找
    binarySearch(arr,left,midIndex-1,findVal)
  }else if(findVal > arr(midIndex)){//向右递归查找
    binarySearch(arr,midIndex+1,right,findVal)
  }else{//查找到，返回下标
    midIndex
  }
}
java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
package com.ys.chazhao;
/*
* 查找数目超过半数的值并打印，如果没有就打印0
*
* 方法二：快速排序，中间的值就是数量为半数的值。
*/

//{1,2,3,2,2,2,5,4,2}
public class Banshuchazhao {
    public static int MoreThanHalfNum_Solution(int[] array) {
        int res = array[0], count = 1;
        for (int i = 1; i < array.length; i++) {
            if (array[i] == res)
                count++;
            else {
                count--;
            }
            if (count == 0) {
                res = array[i];
                count = 1;
            }
        }
        // 验证
        count = 0;
        for (int i = 0; i < array.length; i++) {
            if (array[i] == res)
                count++;
        }
        return count > array.length / 2 ? res : 0;
    }

    public static void main(String[] args) {
        int i = MoreThanHalfNum_Solution(new int[]{1, 2, 3, 2, 2, 2, 5, 4, 2});
        System.out.println(i);

    }
}

拓展需求：当一个有序数组中，有多个相同的数值时，如何将所有的数值都查找到。

代码实现如下：

scala
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/*
  {1,8, 10, 89, 1000, 1000，1234} 当一个有序数组中，有多个相同的数值时，如何将所有的数值都查找到，比如这里的 1000.
  //分析
  1. 返回的结果是一个可变数组 ArrayBuffer
  2. 在找到结果时，向左边扫描，向右边扫描 [条件]
  3. 找到结果后，就加入到ArrayBuffer
   */
  def binarySearch2(arr: Array[Int], l: Int, r: Int,
                    findVal: Int): ArrayBuffer[Int] = {

    //找不到条件?
    if (l > r) {
      return ArrayBuffer()
    }

    val midIndex = (l + r) / 2
    val midVal = arr(midIndex)
    if (midVal > findVal) {
      //向左进行递归查找
      binarySearch2(arr, l, midIndex - 1, findVal)
    } else if (midVal < findVal) { //向右进行递归查找
      binarySearch2(arr, midIndex + 1, r, findVal)
    } else {
      println("midIndex=" + midIndex)
      //定义一个可变数组
      val resArr = ArrayBuffer[Int]()
      //向左边扫描
      var temp = midIndex - 1
      breakable {
        while (true) {
          if (temp < 0 || arr(temp) != findVal) {
            break()
          }
          if (arr(temp) == findVal) {
            resArr.append(temp)
          }
          temp -= 1
        }
      }
      //将中间这个索引加入
      resArr.append(midIndex)
      //向右边扫描
      temp = midIndex + 1
      breakable {
        while (true) {
          if (temp > arr.length - 1 || arr(temp) != findVal) {
            break()
          }
          if (arr(temp) == findVal) {
            resArr.append(temp)
          }
          temp += 1
        }
      }
      return resArr
    }

二叉树相关

二叉树的特点

（1）树执行查找、删除、插入的时间复杂度都是O(logN)

（2）遍历二叉树的方法包括前序、中序、后序

（3）非平衡树指的是根的左右两边的子节点的数量不一致

（4）在非空二叉树中，第i层的结点总数不超过 , i>=1；

（5）深度为h的二叉树最多有个结点(h>=1)，最少有h个结点；

（6）对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；

定义节点以及前序、中序、后序遍历

scala
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
class TreeNode(treeNo:Int){

  val no = treeNo
  var left:TreeNode = null
  var right:TreeNode = null

  //后序遍历
  def postOrder():Unit={
    //向左递归输出左子树
    if(this.left != null){
      this.left.postOrder
    }
    //向右递归输出右子树
    if (this.right != null) {
      this.right.postOrder
    }

    //输出当前节点值
    printf("节点信息 no=%d \n",no)
  }

  //中序遍历
  def infixOrder():Unit={
    //向左递归输出左子树
    if(this.left != null){
      this.left.infixOrder()
    }

    //输出当前节点值
    printf("节点信息 no=%d \n",no)

    //向右递归输出右子树
    if (this.right != null) {
      this.right.infixOrder()
    }
  }

  //前序遍历
  def preOrder():Unit={
    //输出当前节点值
    printf("节点信息 no=%d \n",no)

    //向左递归输出左子树
    if(this.left != null){
      this.left.postOrder()
    }

    //向右递归输出右子树
    if (this.right != null) {
      this.right.preOrder()
    }
  }

  //后序遍历查找
  def postOrderSearch(no:Int): TreeNode = {
    //向左递归输出左子树
    var resNode:TreeNode = null
    if (this.left != null) {
      resNode = this.left.postOrderSearch(no)
    }
    if (resNode != null) {
      return resNode
    }
    if (this.right != null) {
      resNode = this.right.postOrderSearch(no)
    }
    if (resNode != null) {
      return resNode
    }
    println("ttt~~")
    if (this.no == no) {
      return this
    }
    resNode
  }

  //中序遍历查找
  def infixOrderSearch(no:Int): TreeNode = {


    var resNode : TreeNode = null
    //先向左递归查找
    if (this.left != null) {
      resNode = this.left.infixOrderSearch(no)
    }
    if (resNode != null) {
      return resNode
    }
    println("yyy~~")
    if (no == this.no) {
      return this
    }
    //向右递归查找
    if (this.right != null) {
      resNode = this.right.infixOrderSearch(no)
    }
    return resNode

  }

  //前序查找
  def preOrderSearch(no:Int): TreeNode = {
    if (no == this.no) {
      return this
    }
    //向左递归查找
    var resNode : TreeNode = null
    if (this.left != null) {
      resNode = this.left.preOrderSearch(no)
    }
    if (resNode != null){
      return  resNode
    }
    //向右边递归查找
    if (this.right != null) {
      resNode = this.right.preOrderSearch(no)
    }

    return resNode
  }

  //删除节点
  //删除节点规则
  //1如果删除的节点是叶子节点，则删除该节点
  //2如果删除的节点是非叶子节点，则删除该子树

  def delNode(no:Int): Unit = {
    //首先比较当前节点的左子节点是否为要删除的节点
    if (this.left != null && this.left.no == no) {
      this.left = null
      return
    }
    //比较当前节点的右子节点是否为要删除的节点
    if (this.right != null && this.right.no == no) {
      this.right = null
      return
    }
    //向左递归删除
    if (this.left != null) {
      this.left.delNode(no)
    }
    //向右递归删除
    if (this.right != null) {
      this.right.delNode(no)
    }
  }
}

定义二叉树，前序、中序、后序遍历，前序、中序、后序查找，删除节点

scala
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
class BinaryTree{
  var root:TreeNode = null

  //后序遍历
  def postOrder(): Unit = {
    if (root != null){
      root.postOrder()
    }else {
      println("当前二叉树为空，不能遍历")
}
}
    //中序遍历
    def infixOrder(): Unit = {
      if (root != null){
        root.infixOrder()
      }else {
        println("当前二叉树为空，不能遍历")
      }
    }
    //前序遍历
    def preOrder(): Unit = {
      if (root != null){
        root.preOrder()
      }else {
        println("当前二叉树为空，不能遍历")
      }
    }

    //后序遍历查找
    def postOrderSearch(no:Int): TreeNode = {
      if (root != null) {
        root.postOrderSearch(no)
      }else{
        null
      }
    }

    //中序遍历查找
    def infixOrderSeacher(no:Int): TreeNode = {
      if (root != null) {
        return root.infixOrderSearch(no)
      }else {
        return null
      }
    }

    //前序查找
    def preOrderSearch(no:Int): TreeNode = {

      if (root != null) {
        return root.preOrderSearch(no)
      }else{
        //println("当前二叉树为空，不能查找")
        return null
      }
    }
//删除节点
    def delNode(no:Int): Unit = {
      if (root != null) {
        //先处理一下root是不是要删除的
        if (root.no == no){
          root = null
        }else {
          root.delNode(no)
        }
      }
    
  }
文章作者: Yang4
文章链接: https://masteryang4.github.io/2020/06/15/%E5%B8%B8%E7%94%A8%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E6%80%BB%E7%BB%93/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 MasterYangBlog！
面试 算法与数据结构
打赏
  • 微信
    微信
  • 支付宝
    支付宝
相关推荐
2020-03-22
LeetCode经典10道题
2020-05-12
[精]Redis总结与思考
2020-06-17
sqoop常见问题汇总
2020-06-16
Spark的WordCount到底有几个RDD
2020-06-07
Redis常见问题及扩展
2020-05-26
一段有趣的spark_aggregate代码
评论
简