JavaSE-数据结构和排序算法

数据结构：

• 编程的本质就是对数据(信息以数据的形式而存在)的处理，实际编程中不得不处理大量的数据，因此实际动手编程之前必须先分析这些数据，处理数据之间存在的关系。
• 现实的数据元素之间有着纷繁复杂的逻辑关系，需要采用和是的物理结构来存储这些数据，并以此为基础，对这些数据进行相应的操作。同时，还要分析这些数据结构在时间，空间上的开销的优势。
• 这种专门研究应用程序中数据之间逻辑关系，存储方式及其操作的学问就是数据结构。

逻辑结构：

• Data-Structure = （D,R）

• 数据元素之间存在的关联关系被称为数据的逻辑结构。归纳起来，应用程序中的数据大致有如下四种基本的逻辑结构：

• 集合：数据元素之间只有“同数据一个集合”的关系

• 线性关系：数据元素之间存在一个对一个的关系

• 树状结构：数据元素之间存在一个对多个的关系

• 图状结构或网状结构：数据元素之间存在多个对多个的关系。
  

排序算法

• 排序：假设含有几个记录的序列为{R1,R2,...,Rn},其相应的关键字序列为{k1,k2,...,k3}。将这些记录重新排序为{Ri1,Ri2,...,Rin},使得相应的关键字值满足ki1<=ki2<=...<=kin,这样的一种操作称为排序。
• 通常来说，排序的目的是快速查找。

衡量排序算法的优劣：

• 时间复杂度：分析关键字的比较次数和记录的移动次数。
• 空间复杂度：分析排序算法中需要多少辅助内存。
• 稳定性：若两个记录A和B的关键字值相等，但排序后A，B的先后次序保持不变，则称这种排序算法是稳定的。

常用的排序

• 选择排序：直接选择排序，堆排序
• 交换排序：冒泡排序，快速排序
• 插入排序：直接插入排序，折半插入排序，shell排序
• 归并排序：桶式排序，基数排序

排序：Arrays.sort();//工具类

• 选择排序：在要排序的一组数中，选出最小的一个数与第一个位置的数交换，然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。

  public static void selectSort(int[] arr){
      for(int i = 0; i < arr.length; i++){
          int k = i;//待确定的位置
          for(int j = arr.length-1; j > i; j--){
              if(arr[j] < arr[k]){
                  k = j;//记录第i个最小值位置
              }
          }
          //将第i个位置的元素与此轮找到最小的值交换
          int temp = arr[i];
          arr[i] = arr[k];
          arr[k] = temp;
      }
  }
  

• 冒泡排序：比较相邻两个元素的大小，如果后一个元素比前一个元素小，则交换两个元素的位置。一轮之后最大的元素会沉到底部。小的元素会逐渐往上浮，故称为冒泡排序。

  public static void bubbleSort(int[] arr){
      int temp = 0;                    //起始比较位置
      int size = arr.length;            //数组的元素个数
      for(int i = 0; j < size-1; i++){//外层控制轮次
          for(int j = 0; j < size-1-j; j++){//内层进行比较
              if(arr[j] > a[j+1]){
                  temp = arr[j];
                  arr[j] = arr[j+1];
                  arr[j+1] = temp;
              }
          }
      }
  }
  

• 插入排序：每步将一个待排序的记录，按其顺序码大小插入到前面已经排序的字序列的合适位置(从后向前找到合适位置后),知道全部插入排序完为止。

  public static void insertSort(int[] arr){
      int size = arr.length;
      int temp = 0;
      int j = 0;
      for(int i = 0; i < size; i++){
          temp = arr[i];
          //假如temp比前面的值小，则将前面的值后移
          for(j = i; j > 0 && temp < arr[j-1]; j--){
              arr[j] = arr[j-1];
          }
          arr[j] = temp;
      }
  }