术语说明

  • 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；
  • 不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；
  • 内排序：所有排序操作都在内存中完成；
  • 外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；
  • 时间复杂度： 一个算法执行所耗费的时间。

  • 空间复杂度：运行完一个程序所需内存的大小

    算法总结

    排序以及查找算法总结 - 图1
    图中名词解释：

  • n: 数据规模

  • k: “桶”的个数
  • In-place: 占用常数内存，不占用额外内存
  • Out-place: 占用额外内存

O(N^2)的排序

冒泡排序

冒泡排序每一次头开始遍历，和后面的一个数据进行遍历。每次就可以把最大的数放到后面。也就是说经过N次的操作，我们可以将一个数据放回自己正确的位置。

复杂度分析：
最坏 O（N^2） 最好O（N） 平均： O（N^2）

  1. class Solution {
  2.     public int[] sortArray(int[] nums) {
  3.         if(nums.length ==0) return nums;
  4.         for(int i=0;i<nums.length;i++){
  5.             for(int j=1;j<nums.length-i;j++){
  6.                 if(nums[j]<nums[j-1]){
  7.                     swap(nums,j-1,j);
  8.                 }
  9.             }
  10.         }
  11.         return nums;
  13.     }
  14.     private void swap(int[] nums,int a,int b){
  15.         int tmp = nums[a];
  16.         nums[a] = nums[b];
  17.         nums[b] = tmp;
  18.     }
  19. }

选择排序

选择排序每次我们找到数据里面最小（大）的数据，将这个数据放到该有的位置。选择排序是最为稳定的排序算法之一。因为所有的数据都是需要N^2的复杂度。

查找