第九章 排序【数据结构】【精致版】

#define MAXSIZE 1000  //假设的文件长度,即待排序的记录数目  
typedef int KeyType;  //假设的关键字类型
typedef int OtherType;
typedef struct{
  KeyType key;//关键字项
  OtherType other_data;//其他数据项,类型OtherType依赖于具体应用而定义  
}RecordType; //记录类型
typedef struct{
  RecordType r[ MAXSIZE+1];
  int length;//序列长度,即记录个数
}RecordList; //记录序列类型,即顺序表类型
RecordList create(int nums[],int n){
  RecordList L;
  L.length=n;
  for(int i=1;i<=n;i++){
    RecordType t={nums[i],0};
    L.r[i]=t;
  }
  return L;
}
void print(RecordList L){
  int n=L.length;
  for(int i=1;i<=n;i++){
    printf("%d ",L.r[i].key);
  }
  printf("\n");
}

#include <stdio.h>
#include "0-RecordList.h"
// 【算法9-1】直接插入排序
RecordList insertSort(RecordList L){
    for (int i = 2; i <= L.length; i++){
        L.r[0] = L.r[i]; // 监视哨备份待查记录
        int j;
        for (j = i - 1; L.r[0].key < L.r[j].key; j--){
            L.r[j + 1] = L.r[j]; // 记录后移
        }
        L.r[j + 1] = L.r[0]; // 插入正确位置
    }
    return L;
}
// 待插记录已是当前有序的最大记录，不需要后移排序
// 【算法9-2】改进的直接插入排序
RecordList insertSortPlus(RecordList L){
    for (int i = 2; i <= L.length; i++){
        if (L.r[i].key < L.r[i - 1].key){      // 如果不小于，就是待插记录已是当前有序的最大记录
            L.r[0] = L.r[i]; // 监视哨备份待查记录
            int j;
            for (j = i - 1; L.r[0].key < L.r[j].key; j--){
                L.r[j + 1] = L.r[j]; // 记录后移
            }
            L.r[j + 1] = L.r[0]; // 插入正确位置
        }
    }
    return L;
}

int main(){
    int n=8;
    int nums[9]={-1,33,12,25,46,33,68,19,80};//0号不存储元素 
    RecordList L=create(nums,n);
    print(L);//33 12 25 46 33 68 19 80
    print(insertSort(L)); //12 19 25 33 33 46 68 80  
    print(insertSortPlus(L)); //12 19 25 33 33 46 68 80
}

#include <stdio.h>
#include "0-RecordList.h"
//【算法9-3】折半插入排序
//因为插入到有序列中，有折半快速找到位置
RecordList biInsertSort(RecordList L){
    for (int i = 2; i <=L.length ; i++) {
        if(L.r[i].key<L.r[i-1].key){//如果不小于，就是待插记录已是当前有序的最大记录
            L.r[0]=L.r[i];//监视哨备份待查记录
            //折半查找nums[i]插入位置
            int low=1;
            int high=i-1;
            while (low<high){
                int mid=(low+high)/2;
                if(L.r[0].key<L.r[mid].key){
                    high=mid-1;
                }else{
                    low=mid+1;
                }
            }
            for (int j = i-1; j>=low; j--) {
                L.r[j+1]=L.r[j];//记录后移
            }
            L.r[low]=L.r[0];//插入正确位置
      }
    }
    return L; 
}

int main(){
    int n=8;
    int nums[9]={-1,33,12,25,46,33,68,19,80};//0号不存储元素 
    RecordList L=create(nums,n);
    print(L);//33 12 25 46 33 68 19 80
    print(biInsertSort(L)); //12 19 25 33 33 46 68 80   
}

#include <stdio.h>
#include "0-RecordList.h"
#include <stdio.h>
#include "0-RecordList.h"
//【算法9-4】希尔排序
//最小增量排序
void shellInsert(RecordList* L,int dk){
    for (int i = dk+1; i<=L->length ; i++) {
        if(L->r[i].key<L->r[i-1].key){//如果不小于，就是待插记录已是当前有序的最大记录
            L->r[0]=L->r[i];//监视哨备份待查记录
            int j;
            for (j = i-dk; j>0&&L->r[0].key<L->r[j].key; j-=dk) {
                L->r[j+dk]=L->r[j];//记录后移
            }
            L->r[j+dk]=L->r[0];//插入正确位置
        }
    }
}
//dlta 增量序列
void shellSort(RecordList* L,int dlta[],int t){//t为增量序列的长度
    for (int k=0;k<t;k++){
        shellInsert(L,dlta[k]);
    }
}

int main(){
    int n=8;
    int nums[9]={-1,46,25,68,33,33,19,12,80};//0号不存储元素 
    RecordList L=create(nums,n);
    print(L);//46 25 68 33 33 19 12 80
//    int dlta[3]={4,2,1};
    int dlta[3]={7,3,1};
    int t=3;
    shellSort(&L,dlta,t); 
  print(L);//12 19 25 33 33 46 68 80 
}

#include <stdio.h>
#include "0-RecordList.h"
//【算法9-5】冒泡排序
RecordList bubbleSort(RecordList L){
    for (int i = 1; i <= L.length; i++) {
        for (int j = 1; j <=L.length-i ; j++) {
            if(L.r[j].key>L.r[j+1].key){
                RecordType temp=L.r[j];
                L.r[j]=L.r[j+1];
                L.r[j+1]=temp;
            }
        }
    }
    return L; 
}
//【算法9-6】改进冒泡排序
//如已排好序，直接跳出
RecordList bubbleSortPlus(RecordList L){
    int flag=1;
    for (int i = 1; i <= L.length&&flag; i++) {
        flag=0;
        for (int j = 1; j <=L.length-i ; j++) {
            if(L.r[j].key>L.r[j+1].key){
                RecordType temp=L.r[j];
                L.r[j]=L.r[j+1];
                L.r[j+1]=temp;
                flag=1;
            }
        }
    }
    return L;
}

int main(){
    int n=8;
    int nums[9]={-1,46,25,68,33,33,19,12,80};//0号不存储元素 
    RecordList L=create(nums,n);
    print(L);//46 25 68 33 33 19 12 80
    print(bubbleSort(L));     //12 19 25 33 33 46 68 80      
    print(bubbleSortPlus(L));   //12 19 25 33 33 46 68 80   
}

#include <stdio.h>
#include "0-RecordList.h"
//【算法9-7】一趟快速排序 
int QKPass(RecordList* L,int low,int high){
    L->r[0]=L->r[low];//枢轴
    while(low<high){
        while (low<high&&L->r[high].key>=L->r[0].key) --high;
        L->r[low]=L->r[high];
        while (low<high&&L->r[low].key<L->r[0].key) ++low;
        L->r[high]=L->r[low];
    }
    L->r[low]=L->r[0];
    return low;
}
//【算法9-8】快速排序 
void QKSort(RecordList* L,int low,int high){
    int pos;
    if (low<high){
        pos=QKPass(L, low,high);
        QKSort(L, low,pos-1);
        QKSort(L, pos+1,high);
    }
}

int main(){
    int n=8;
    int nums[9]={-1,46,68,12,25,33,80,19,33};//0号不存储元素 
    RecordList L=create(nums,n);
    print(L);//46 68 12 25 33 80 19 33   
    QKSort(&L,1,L.length);        
  print(L);//12 19 25 33 33 46 68 80
}

#include <stdio.h>
#include "0-RecordList.h"
//【算法9-9】简单选择排序
RecordList selectSort(RecordList L){
    for (int i = 1; i <= L.length; i++) {
        int k=i;
        for (int j = i+1; j <=L.length ; j++) {
            if (L.r[j].key<L.r[k].key){//k是擂台
                k=j;
            }
        }
        if (k!=i){
            RecordType temp=L.r[i];
            L.r[i]=L.r[k];
            L.r[k]=temp;
        }
    }
    return L;
}

int main(){
    int n=8;
    int nums[9]={-1,33,68,46,33,25,80,19,12};//0号不存储元素 
    RecordList L=create(nums,n);
    print(L);//33 68 46 33 25 80 19 12
    print(selectSort(L));     //12 19 25 33 33 46 68 80   
}

#include <stdio.h>
#include "0-RecordList.h"
//【算法9-10】堆的筛选
void HeapAdjust(RecordList* L,int s,int m){
    //已知L[s..m]中记录的关键字除L[s]之外均满足堆的定义
    //本函数调整L[s]的关键字，使L[s..m]成为小顶堆
    RecordType t=L->r[s];
    for(int j=2*s;j<=m;j*=2){
        //沿key较小的孩子结点向下筛选
        if(j<m&&L->r[j].key>L->r[j+1].key){
            j++;//j为key较小的记录的下标
        }
        if(t.key<=L->r[j].key){
            break;
        }
        //t应该插入位置s
        L->r[s]=L->r[j];
        s=j;
    }
    L->r[s]=t;
}
//【算法9-11】建立初始堆
void CreatHeap(RecordList* L){
    int len=L->length;
    for (int i=len/2;i>=1;i--){
        HeapAdjust(L,i, len);
    }
}
//【算法9-12】堆排序
void HeapSort(RecordList* L){
    CreatHeap(L);
    int len= L->length;
    for (int i = len; i >=2 ; i--) {
        L->r[0]=L->r[1];
        L->r[1]=L->r[i];
        L->r[i]=L->r[0];
        HeapAdjust(L,1,i-1);
    }
}

int main(){
    int n=8;
    int nums[9]={-1,46,12,33,72,68,19,80,33};//0号不存储元素 
    RecordList L=create(nums,n);
    print(L);//46 12 33 72 68 19 80 33   
    HeapSort(&L);        
    print(L);//80 72 68 46 33 33 19 12
}

#include <stdio.h>
#include "0-RecordList.h"
void Merge(RecordList* ,RecordList* ,int ,int ,int );
//【算法9-13】二路归并排序
void MergeSort(RecordList* L,RecordList* CopyL,int left,int right){
    //对上下限值分别为left和right的记录序列L进行归并排序
    //其中copyL为同类型的记录，由于复制保存原记录序列
    int middle;
    if(left<right){
        middle=(left+right)/2;//找中间位置进行划分
        MergeSort(L,CopyL,left,middle);//对左半部分进行递归归并排序
        MergeSort(L,CopyL,middle+1,right);//对右半部分进行递归 归并排序
        Merge(L,CopyL,left,right,middle);//进行归并
    }
}
//【算法9-14】二路归并排序
void Merge(RecordList* L,RecordList* CopyL,int left,int right,int middle){
    int i,p1,p2;
    for (i=left;i<=right;i++){//用copyL记录临时保存待排序记录序列
        CopyL->r[i]=L->r[i];
    }
    p1=left;//左半部分有序记录的起始位置
    p2=middle+1;//右半部分有序记录的起始位置
    i=left;//左半部分开始进行归并
    while(p1<=middle&&p2<=right){
        //取两个有序半区中关键字较小的记录
        if (CopyL->r[p1].key<=CopyL->r[p2].key){
            L->r[i]=CopyL->r[p1];//去较小的记录放到合并后的记录序列中
            p1++;
        } else{
            L->r[i]=CopyL->r[p2];
            p2++;
        }
        i++;
    }
    //剩下的序列无论是左半部分还是右半部分都直接复制到合并后的记录序列中
    while (p1<=middle){
        L->r[i]=CopyL->r[p1];
        i++;
        p1++;
    }
    while (p2<=middle){
        L->r[i]=CopyL->r[p2];
        i++;
        p2++;
    }
}
int main(){
    int n=8;
    int nums[9]={-1,46,12,33,72,68,19,80,33};//0号不存储元素 
    RecordList L=create(nums,n);
    print(L);//46 12 33 72 68 19 80 33
  RecordList CopyL=create(nums,n);
    MergeSort(&L,&CopyL,0,n);        
    print(L);//12 19 33 33 46 68 72 80
}

#include <stdio.h>
#include <stdlib.h> 
#include "0-RecordList.h"
//【算法9-15】自然归并排序
//将两个有序的子序列R[low..m]和R[m+1..high]归并成一个有序的子序列R[low..high]
void Merge(RecordType* R,int l,int m,int r){
    int i=l,j=m+1,p=0,q;
  RecordType *R1;
  R1=(RecordType*) malloc((r-l+1)*sizeof(RecordType));
  if(!R1) return;//申请空间失败 
    while (i<=m&&j<=r){
        //取两个有序半区中关键字较小的记录
        if(R[i].key<=R[j].key){
            R1[p++]=R[i++];
        }else {
            R1[p++]=R[j++];
        }
    }
    //剩下的序列无论是左半部分还是右半部分都直接复制到合并后的记录序列中
    if (i>m){
        for (q = j; q <=r ; q++) {
            R1[p++]=R[q];
        }
    }else {
        for (q=i;q<=m;q++){
            R1[p++]=R[q];
        }
    }
    for (p=0,i=l;i<=r;p++,i++){
        R[i]=R1[p];//归并完成后将结果复制回R[low..high]
    }
}
void NatureMergeSort(RecordType R[],int n){
    int i,sum,low,mid,high;
    while (1){
        i=0;
        sum=1;
        while (i<n-1){
            low=i;
            while (i<n-1&&R[i].key<R[i+1].key){ i++; }
            mid=i++;
            while (i<n-1&&R[i].key<R[i+1].key){ i++; }
            high=i++;
            if (i<=n){
                Merge(R,low,mid,high);
                sum++;
            }
        }
        if (sum==1) break;
    }
}

int main(){
    int n=8;
    int nums[9]={-1,12,24,5,8,3,9,11,7};//0号不存储元素 
    RecordList L=create(nums,n);
    print(L);//12 24 5 8 3 9 11 7
  RecordList CopyL=create(nums,n);
    NatureMergeSort(L.r,9);        
    print(L);//3 5 7 8 9 11 12 24
}

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include <time.h>
/*
Heart 红桃 
Spade 黑桃 
club  梅花 
diamond 方块 
*/
//花色的枚举类 
typedef enum color{
  D=1,C,S,H
}Color; 
//扑克的定义 
typedef struct card{
  Color color;
  int num;
}Card;
//输出花色 
void printColor(Color c){
  switch(c){
    case H: printf("红桃");break;
    case S: printf("黑桃");break;
    case C: printf("梅花");break;
    case D: printf("方块");break;
  }
}
//输出扑克 
void printCard(Card card){
  printColor(card.color);
  printf("%-2d",card.num);
} 
//创建一幅扑克 
void creatCards(Card cards[52]){  
    int colors[4]={D,C,S,H};
    int nums[13]={1,2,3,4,5,6,7,8,9,10,11,12,13};
    int n=0;
    for(int i=0;i<4;i++){
        for(int j=0;j<13;j++){
          Card card;
          card.color=colors[i];
          card.num=nums[j];
          cards[n]=card;   
      n++;  
    }
    }
//    printCards(cards);
}
//洗牌 
void shuffleCards(Card cards[52]){  
  srand((unsigned)time(NULL));//用srand()函数来重新播种，用time来充当随机数种子 
  creatCards(cards);  
  //交换52次 
  for (int i=0;i<52;i++){
    int r1=rand()%52;//rand()函数产生的随机数是伪随机数 ，和种子有关 
    int r2=rand()%52;
    //交换两张牌 
    Card temp=cards[r1];
    cards[r1]=cards[r2];
    cards[r2]=temp;
  }
} 
//打印扑克牌 
void printCards(Card cards[52]){
  for(int i=0;i<52;i++){
    printCard(cards[i]);
    printf(" ");
    if(i%13==12){
      printf("\n");
    }
  }
}
//按最高位优先法MSD排序  花色从小到大  数值从小到大 
void sortCardsWithMSD(Card cards[52]){
  printf("按最高位优先法LSD排序 \n"); 
  //首先按照花色将整副牌分为4组（每组13张牌）
  Card cardsByColor[4][13];
  int cardColorCount[4]={0}; //一个计数器数组，用来记录每组花色加入了多少 
  for (int i=0;i<52;i++){
    int index=cards[i].color-1; //面值从1开始，索引是从0开始的 
    cardsByColor[index][cardColorCount[index]]=cards[i];
    cardColorCount[index]++;    
  } 
//  printf("测试1\n");
//  for(int i=0;i<4;i++){
//    for(int j=0;j<13;j++){
//      printCard(cardsByColor[i][j]); 
//    }   
//    printf("\n");
//  }
  //然后每组在按照面值从小到大进行排序 (选择排序） 
  for(int i=0;i<4;i++){   
    for(int j=0;j<13;j++){
      int m=j; 
      for(int k=j+1;k<13;k++){
        if(cardsByColor[i][k].num<cardsByColor[i][m].num){
          m=k;
        }
      }
      if(m!=j){       
        Card temp=cardsByColor[i][j];
        cardsByColor[i][j]=cardsByColor[i][m];
        cardsByColor[i][m]=temp;
      }
    }       
  }
//  printf("测试2\n");
//  for(int i=0;i<4;i++){
//    for(int j=0;j<13;j++){
//      printCard(cardsByColor[i][j]); 
//    }   
//    printf("\n");
//  }
  int n=0;
  //最后将这4组牌收集到一起就是按照花色和面值排好序的有序序列 
  for(int i=0;i<4;i++){
    for(int j=0;j<13;j++){
      cards[n]=cardsByColor[i][j];
      n++;
    }   
  }
}
//按最低位优先法LSD排序  花色从小到大  数值从小到大 
void sortCardsWithLSD(Card cards[52]){
  printf("按最低位优先法LSD排序 \n"); 
  //第一步 先按照面值大小从小到大将整副牌分为13组（每组4张牌） 
  Card cardsByNum[13][4]; 
  int cardNumCount[13]={0};//一个计数器数组，用来记录每组面值加入了多少 
  for (int i=0;i<52;i++){
    int index=cards[i].num-1; //面值从1开始，索引是从0开始的 
    cardsByNum[index][cardNumCount[index]]=cards[i];    
    cardNumCount[index]++;    
  } 
//  printf("测试1\n");
//  for(int i=0;i<13;i++){
//    for(int j=0;j<4;j++){
//      printCard(cardsByNum[i][j]); 
//    }   
//    printf("\n");
//  }
  //第二步 然后将每组牌按照面值的大小收集到一起   从小到大 
  Card CollectByNum[52];  
  int n=0;
  for(int i=0;i<13;i++){
    for(int j=0;j<4;j++){
      CollectByNum[n]=cardsByNum[i][j];
      n++;
    }   
  }
//  printf("测试2\n");
//  printCards(CollectByNum);
  //第三步 再对这些牌按照花色摆成4组，每组13张牌    
  Card cardsByColor[4][13];
  int cardColorCount[4]={0}; //一个计数器数组，用来记录每组花色加入了多少 
  for (int i=0;i<52;i++){
    int index=CollectByNum[i].color-1;
    cardsByColor[index][cardColorCount[index]]=CollectByNum[i];
    cardColorCount[index]++;    
  } 
//  printf("测试3\n");
//  for(int i=0;i<4;i++){
//    for(int j=0;j<13;j++){
//      printCard(cardsByColor[i][j]); 
//    }   
//    printf("\n");
//  }
  n=0;
  //第四步 最后再把4组牌按花色的次序收集到一起就是按照花色和面值排好序的有序序列 
  for(int i=0;i<4;i++){
    for(int j=0;j<13;j++){
      cards[n]=cardsByColor[i][j];
      n++;
    }   
  }
//  printf("4");
}
void sortCardsWithBinSort(Card cards[52]){
  printf("按桶排序 \n"); 
  //首先按照花色将整副牌分为4组（每组13张牌）  
  Card cardsByBin[4][13];
  //然后每组在按照面值从小到大进行排序 (桶排序）
  for (int n=0;n<52;n++){
    int i=cards[n].color-1;
    int j=cards[n].num-1;
    cardsByBin[i][j]=cards[n];        
  } 
  int n=0;
  //最后将这4组牌收集到一起就是按照花色和面值排好序的有序序列 
    for(int i=0;i<4;i++){
    for(int j=0;j<13;j++){
      cards[n]=cardsByBin[i][j];
      n++;
    }   
  }
}
void main(){
  printf("排序 按照花色从小到大  数值从小到大 \n");
    Card cards[52] ;   
    printf("洗牌ing.....\n");
  shuffleCards(cards);  //洗牌 
  printf("排序前的牌\n");
  printCards(cards);    //打印扑克牌 
  printf("排序ing.....\n"); 
//  sortCardsWithLSD(cards);//排序 
//  sortCardsWithMSD(cards);//排序 
  sortCardsWithBinSort(cards);
  printf("排序后的牌\n");
  printCards(cards);    //打印扑克牌 
}

#include <stdio.h>
#include <stdlib.h> 
#include "0-RecordList.h"
typedef RecordType DataType; 
#include "链队列.c"
int digit(KeyType key, int m, int r);
//【算法9-16】基于链队列的基数排序
void RadixSort(RecordType L[] ,int n,int m,int r){
    //L中的关键字为m为r进制数，L的长度为n
    LQueue** Queue;
    int i,j,k;
    Queue=(LQueue**)malloc(r*sizeof(LQueue*));
    for(i=0;i<r;i++){               //初始化r个链队列
        Queue[i]=Init_LQueue();
  }
    for (i = 0;  i<m ; i++) {       //进行m次分配与收集
        for (j=0;j<=n;j++){          //分配
            k=digit(L[j].key,i,r);   //提取当前关键字中第m位的数字值
            InLQueue(Queue[k],L[j]);
        }
        k=0;
        for (j = 0; j < r; j++) {   //收集
            for ( ; !Empty_LQueue(Queue[j]); k++) {
                Out_LQueue(Queue[j],&(L[k]));
            }
        }
    }
}
//【算法9-17】提取关键字中第m位的数字值
int digit(KeyType key, int m, int r){
    int i,d;
    if(m==0){
        return key %r;
    }
    d=r;
    for (i = 1;  i<m ; i++) {
        d*=r;
    }
    return ((int)(key/d)%r);
}

int main(){
    int n=9;
    int nums[10]={-1,921,435,628,285,862,225,448,193,430};//0号不存储元素 
    RecordList L=create(nums,n);
    print(L);//921 435 628 285 862 225 448 193 430
    RadixSort(L.r,9,3,10);       
    print(L);//193 225 285 430 435 448 628 862 921
}