Java算法大全五-查找排序

一、直接插入排序

• 插入排序基本思想是每次将一个待排序的记录按其关键字大小插入到前面已排好序的子序列中，直到全部记录插入完成
• 比较次数和移动次数取决于待排序表的初始状态
• 适用于顺序存储和链式存储的线性表

void insertSort(int[] arr){
    int i,j;
    int n = arr.length;
    for(i=2;i<=n;i++){          // 依次将A[2]~A[n]插入到前面已排序序列
        if(A[i]<A[i-1]){        // 若A[i]关键码小于其前驱，将A[i]插入有序表中
            A[0]=A[i];          // 复制为哨兵，A[0]不存放元素
            for(j=i-1;A[0]<A[j];--j)    // 从后往前查找待插入位置
                A[j+1]=A[j];    // 向后挪位
            A[j+1]=A[0];        // 复制到插入位置
        }
    }
}

二、折半插入排序

• 设在待排序表中有一个记录序列V[1], …,v[n]。其中V[1], …, v[i-1]是已经排好序的记录。在插入v[i]时，利用折半搜索法寻找 v[i] 的插入位置，并插入，直到所有记录插入完成
• 比较次数与待排序表的初始状态无关，仅取决于表中的元素个数n
• 元素的移动次数未改变，依赖于待排序表的初始状态
• 是一种稳定的排序算法

void InsertSort(ElemType A[],int n){
    int i,j,low,high,mid;
    for(i=2;i<=n;i++){          // 依次将A[2]~A[n]插入前面的已排序序列
        A[0]=A[i];              // 将A[i]暂存到A[0]
        low=1;high=i-1;         // 设置折半查找的范围
        while(low<=high){       // 折半查找（，默认递增有序）
            mid=(low+high)/2;   // 取中间点
            if(A[mid]>A[0])     // 查找左半子表
                high=mid-1;     // 查找右半子表
            else
                low=mid+1;
        }
        for(j=i-1;j>=high+1;--j)
            A[j+1]=A[j];        // 统一后移元素，空出插入位置
        A[high+1]=A[0];         // 插入操作
    }
}

三、希尔排序

• 先将待排序表分割成若干形如L[i,i+d,i+2d,…,i+kd]的“特殊”子表，即把相隔某个“增量”的记录组成一个子表，对各个子表分别进行直接插入排序，当整个表中的元素已呈“基本有序”时，再对全体记录进行一次直接插入排序
• 仅适用于线性表为顺序存储的情况

void ShellSort(ElemType A[],int n){
    // A[0]只是暂存单元，不是哨兵，当j<=0时，插入位置已到
    for(dk=n/2;dk>=1;dk=dk/2){  // 步长变化
        for(i=dk+1;i<=n;++i){
            if(A[i]<A[i-dk]){       // 需将A[i]插入有序增量子表
                A[0]=A[i];          // 暂存在A[0]
                for(j=i-dk;j>0&&A[0]<A[j];i-=dk)
                    A[j+dk]=A[j];       // 记录后移，查找插入的位置
                A[j+dk]=A[0]            // 插入
            }
        }
    }
}

四、冒泡排序

• 从后往前（或从前往后）两两比较相邻元素的值，若为逆序（即A[i-1]>A[i]），则交换它们，直到序列比较完。重复这一步骤，直到序列全部有序
• 每一趟排序都能使一个元素放置在其最终的位置上
• 比较次数和移动次数取决于待排序表的初始状态

void BubbleSort(ELemType A[],int n){
    for(i=0;i<n-1;i++){
        flag=false;             // 表示本趟冒泡是否发生交换的标志
        for(j=n-1;j>i;j--){     // 一趟冒泡国产
            if(A[j-1]>A[j]){    // 若为逆序
                swap(A[j-1],A[j]);  // 交换
                flag=true;
            }
        }
        if(flag==false)
            return;         // 本趟遍历后没有发生交换，说明表已经有序
    }
}

五、快速排序

• 在待排序表L[1,2,…,n]中任取一个元素pivot作为基准，通过一趟排序将待排序表划分为独立的两个部分L[1,…,k-1]和L[k+1,…,n]，使得L[1,…,k-1]中的所有元素小于pivot，L[k+1,…,n]中的所有元素大于等于pivot，则pivot放在了其最终位置L(k)上。然后分别递归地对两个子表重复上述过程，直到每个部分只有一个元素或为空为止，即所有元素放在了其最终位置上。
• 每一趟排序都能使一个元素放置在其最终的位置上
• 快速排序是所有内部排序算法中平均性能最优的排序算法
• 初始不够对称，会使得快速排序效率降低；元素基本有序，无法发挥长处

void QuickSort(ElemType A[],int low,int high){
    if(low<high){               // 递归跳出的条件
        int pivotpos=Partition(A,low,high);     // 划分
        QuickSort(A,low,pivotpos-1);        // 依次对两个子表进行递归排序
        QuickSort(A,pivot+1,high);
    }
}

int Partition(ElemType A[],int low,int high){   // 一趟划分
    ElemType pivot=A[low];      // 将当前表中第一个元素设为枢轴，对表进行划分
    while(low<high){        // 循环跳出条件
        while(low<high&&A[high]>=pivot) --high;
        A[low]=A[high];         // 将比枢轴小的元素移动到左端
        while(low<high&&A[low]<pivot)   ++low;
        A[high]=A[low];         // 将比枢轴大的元素移动到右端
    }
    A[low]=pivot;           // 枢轴元素存放到最终位置
    return low;             // 返回存放枢轴的最终位置
}

六、简单选择排序

• 每一趟（如第i趟）在后面n-i+1（i=1,2…,n-1）个待排序元素中选取关键字最小的元素，作为有序子序列的第i个元素，直到第n-1趟做完，待排序元素只剩下一个，就不用再选了
• 移动次数与序列的初始状态有关；比较次数与序列的初始状态无关

void SelectSort(ElemType A[],int n){
    for(i=0;i<n-1;i++){     // 一共进行n-1趟
        min=i;              // 记录最小元素位置
        for(j=i+1;j<n;j++)      // 在A[i,...,n-1]中选择最小的元素
            if(A[j]<A[min]) min=j;      // 更新最小元素位置
        if(min!=i)  swap(A[i],A[min]);      // 封装的swap()函数共移动元素3次
    }
}

七、堆排序

7.1 大根堆/小根堆的定义

• n个关键字序列L[1…n]成为堆，当且仅当该序列满足：
  • （1）L(i)>=L(2i)且L(i)>=L(2i+1)或
  • （2）L(i)<=L(2i)且L(i)<=L(2i+1) (1<=i<=n/2取上界)
• 可以将一维数组视为一颗完全二叉树，满足条件（1）的称为大根堆，大根堆的最大元素放在根结点，且其任意非根结点值小于等于其双亲结点值
• 满足条件（2）的堆称为小根堆，小根堆的定义刚好相反，根结点是最小元素

7.2 堆排序的思路

• 首先将存放L[1,…,n]中的n个元素建成初始堆，由于堆本身的特点（以大根堆为例），堆顶元素就是最大值。输出堆顶元素后，通常将堆底元素送入堆顶，此时根结点已不满足大根堆的形式，堆被破坏，将堆顶元素向下调整使其继续保持大根堆的性质，再输出堆顶元素。如此重复，知道堆中仅剩一个元素为止

八、归并排序

8.1 二路归并排序

• 假定待排序表含有n个记录，则可将其视为n个有序的子表，每个子表的长度为1，然后两两归并，得到n/2(取上限)个长度为2或1的有序表；继续两个归并，如此重复，直到合并为一个长度为n的有序表为止

  ElemType *B=(ElemType *)malloc((n+1)*sizeof(ElemType));     // 辅助数组
  
  void MergeSort(ElemType A[],int low,int high){
      if(low<high){
          int mid=(low+high)/2;   // 从中间划分两个子序列
          MergeSort(A,low,mid);   // 从左侧子序列进行递归排序
          MergeSort(A,mid+1,high);    // 对右侧子序列进行递归排序
          Merge(A,low,mid,high);  // 归并
      }
  }
  
  void Merge(ELemType A[],int low,int mid,int high){
      // 表A的两段A[low...mid]和A[mid+1...high]各自有序，将它们合并成一个有序表
      for(int k=low;k<=high;k++)
          B[k]=A[k];          // 将A中所有元素复制到B中
      for(i=low,j=mid+1,k=i;i<mid&&j<high;k++){
          if(B[i]<=B[j])      // 比较B的左右两段中的元素
              A[k]=B[i++];        // 将较小值复制到A中
          else
              A[k]=B[j++];
      }
      while(i<=mid)
          A[k++]=B[i++];  // 若第一个表未检测完，复制
      while(j<=high)
          A[k++]=B[j++];  // 若第二个表未检测完，复制
  }

九、基数排序