数据结构-排序

#include <stdio.h>

typedef int T;

/*插入排序*/
void InsertSort(T r[],int n) {
  for(int i = 1; i <n; i ++)
     if(r[i]<r[i-1]) {
        T temp = r[i];        /*r[i]保存起来*/
        r[i] = r[i-1];    /*r[i-1]后移一个单元*/

       //从i-2开始，往左扫描，直到找到一个<=temp的j

       int j;
       for(j=i-2; j>=0&&temp<r[j]; j--)
          r[j+1] = r[j];       /*每个元素后移*/

       r[j+1] = temp;    /*最后把r[0]写入*/
     }   
}

/*折半插入排序*/
void BiInsertSort(T R[],int n) {
/* 对序列R[0],...R[n-1]作折半插入排序 */
 T temp; int low,high,m;
 for(int i=1; i<n; ++i ) {
     temp = R[i];   /* 将R[i]暂存到R[0]*/
     low = 0; high = i-1;
     while(low<=high) { 
       /*在R[low..high]中折半查找插入的位置*/
         m = (low+high)/2; /* 折半 */
         if (temp < R[m])
              high = m-1; /* 插入点在低半区*/
         else low = m+1;  /* 插入点在高半区*/ 
     }
     for(int j=i-1; j>=high+1; --j )
        R[j+1] = R[j]; /* 记录后移 */
     R[high+1] = temp; /* 插入 */
  }
}

void Print(T a[],int n){
  for(int i = 0 ; i<n;i++)
    printf("%d ",a[i]);
  printf("\n");
}

int main(){
  T arr[] = {49,38,65,97,76,13,27};
  BiInsertSort(arr,7);
  Print(arr,7);

  T b[] = {49,38,65,97,76,13,27};
  InsertSort(b,7);
  Print(arr,7);
}

#include <stdio.h>
typedef int EType;

int LT(EType a, EType b){
  if(a<b) return 1;
  return 0;
}

/*只要对插入排序稍作修改,使得间隔为d的属于
 一个子序列进行插入就可以了*/
 
void InsertShellPass(EType a[], int n,int d) {
  int i,j; EType t;
  for(i = d; i < n; i ++)
    if(LT(a[i], a[i-d])){    //i比i-d小
      t = a[i];    //用t先保存a[i]的值
      a[i] = a[i-d];   //a[i-d]后移一个单元
    
      //从i-2*d开始，往左扫描，直到找到一个<=t的
      for(j=i-2*d; j>=0&&LT(t,a[j]); j-=d)
        a[j+d] = a[j];       //每个元素后移

      a[j+d] = t;    //最后把t写入j+1位置
  }
}

 void ShellSort(EType a[],int n){
    int ds[] = {7,5,3,1};
    for(int i = 0 ; i<4;i++)
      InsertShellPass(a,n,ds[i]);
 }
void Print(EType a[],int n){
  for(int i = 0 ; i<n;i++)
    printf("%d ",a[i]);
  printf("\n");
}

int main(){
  EType arr[] = {49,38,65,97,76,13,27};
  
  ShellSort(arr,7);
  Print(arr,7);
}

/* Bubble sort */
#include <stdio.h>

typedef int T;

void swap(T *xp, T *yp)
{
    T temp = *xp;
    *xp = *yp;
    *yp = temp;
}

/*
void bubbleSort(T arr[], int n){
   int i, j;
   for (i = n-1; i>0; i--)         
       for (j = 0; j < i; j++) 
           if (arr[j] > arr[j+1])
              swap(&arr[j], &arr[j+1]);
}
*/

void bubbleSort(T a[], int n){
   int i, j,swaped;
   for(i = n-1; i>0; i--){
       swaped = 0;         
       for(j = 0; j < i; j++) 
          if (a[j] > a[j+1]){
              swap(&a[j], &a[j+1]);
              swaped = 1;
          }
       if(swaped) break;
   }
}

/* Function to print an array */
void printArray(T arr[], int size)
{
    int i;
    for (i=0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

/*test above functions*/
int main()
{
    T arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr)/sizeof(arr[0]);
    bubbleSort(arr, n);
    printf("Sorted array: \n");
    printArray(arr, n);
    return 0;
}

#include <stdio.h>

typedef int EType;

int LT(EType a, EType b){
  if(a<b) return 1;
  return 0;
}

void Swap(EType *a, EType *b){
  EType t = *a; *a = *b; *b = t;
}

int Partition(EType data[], int low, int high){
      int pivot      = low;       // 以最左元素为中轴
      EType pivotvalue = data[low]; // 记录中轴的值
      while(low < high) {
          while(low<high && data[high] >= pivotvalue)
              high --; // high向左，直到遇见比pivot小的
          while(low<high && data[low] <= pivotvalue)
              low ++;  // low向右，直到遇见比pivot大的
          // low和high扫描受阻，交换low和high的值
          Swap(&data[low], &data[high]);
      }
      // 交换中轴和low的值（也就是把中轴放置到正确的位置上）
      Swap(&data[pivot], &data[low]);
      return low;
  }

void QSort(EType a[], int low, int high) {
    if(low < high)  {    //待排序数列长度大于1
        int pivotloc = Partition(a, low, high);   
        //对左子序列进行排序
        QSort(a, low, pivotloc - 1);
        //对右子序列进行排序
        QSort(a, pivotloc + 1, high);         
    }
}


void Print(EType a[],int n){
   for(int i = 0 ; i<n;i++)
    printf("%d\t",a[i]);
   printf("\n");
}
int main(){
  EType arr[] = {49,38,65,97,76,13,27};
  Print(arr,7);

  QSort(arr,0,6);
  Print(arr,7);
}

#include <stdio.h>
typedef int EType;

int LT(EType a, EType b){
  if(a<b) return 1;
  return 0;
}

void Swap(EType *a, EType *b){
  EType t = *a; *a = *b; *b = t;
}

void SelectSort(EType data[], int n) {
    for(int i = 0; i < n; i ++) {
  // 找到i~n-1中最小的一个IndexMin
     int IndexMin = i;
     for(int j = i; j < n; j ++)
        if(LT(data[j], data[IndexMin]))
           IndexMin = j;
           // 把IndexMin和i作交换
     if(IndexMin != i)
        Swap(&data[IndexMin],&data[i]);
  }
}


void Print(EType a[],int n){
   for(int i = 0 ; i<n;i++)
    printf("%d\t",a[i]);
   printf("\n");
}
int main(){
  EType arr[] = {49,38,65,97,76,13,27};
  Print(arr,7);

  SelectSort(arr,7);
  Print(arr,7);
}