常用数据结构和算法

Posted on | In

排序算法

冒泡排序

  • 需要 array.length-1 轮的比较，可以通过优化标识来减少比较的次数，时间复杂度O(n^2)

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public void bubbleSort(int[] array){
  int temp = 0;
  boolean flag = false;//优化标识
  for(int j = 0; j<array.length - 1; j++){
    for(int i = 0; i<array.length - (j+1); i++){
      if(array[i] > array[i+1]){
        flag = true;
        temp = array[i];
        array[i] = array[i+1];
        array[i+1] = temp;
      }
    }
    if(flag){//发生过交换
      flag = false;
    }else{
      break;
    }
  }
}


快速排序

思路：

  • 1．先从数列中取出一个数作为基准数。
  • 2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
  • 3．再对左右区间重复第二步，直到各区间只有一个数。

quickSort

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
public void quickSort(int[] array, int i, int j){
  if(i > j) {
    return;
  }else{
    int index = getPosition(array, i, j);
    quickSort(array, i, index-1);
    quickSort(array, index+1, j);
  } 
}

//1.找到基准对应的索引
//2.对数据分成两部分，大于基准在右侧；小于基准在左侧
public int getPosition(int[] array, int i, int j){
  int temp = array[j];
  while(i < j){
    while(array[i] <= temp && i < j){
      i++;
    }
    array[j] = array[i];
    
    while(array[j] > temp && i < j){
      j--;
    }
    array[i] = array[j];
  }
  // 跳出循环时low和high相等,此时的low或high就是tmp的正确索引位置
  array[i] = temp;
  return i;
}


查找算法

二分查找

必须是有序数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int binarySearch(int[] array, int target){
  int i = 0;
  int j = array.length-1;
  int mid = 0;
  while(i <= j){
    mid = i + (j-i)/2;
    if(array[mid] == target){
      return mid;
    }else if(array[mid] < target){
      i = mid + 1;
    }else{
      j = mid - 1;
    }
  }
  return -1;	
}

变种：二分查找找最左

可以用来查找相同元素的个数

二分找最左

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int binarySearchForLeft(int[] array, int target){
  int i = 0;
  int j = array.length-1;
  int mid= 0;
  
  while(i < j){
    mid = i + (j-i)/2;
    if(array[mid] >= target){
      j = mid;
    }else{
      i = mid + 1;
    }
  }
  return i;
}

注意：为了验证有没有查找到，需要在调用端判断一下返回位置上的值和 key 是否相等