Sorting Algorithms

#include<stdio.h>
#include<stdlib.h>

//方式一，每次append最小的数到“有序区”的后面。数组前部分为有序区，后部分为无序区。
void bubble_sort1(int a[], int n) {
    int i,j;
    int tmp;
    for (i=0; i<n; i++) {
        for (j=n-1; j>i; j--) {  //从后向前“冒出”最小的数。
            if (a[j-1] > a[j]) {
                tmp = a[j-1];
                a[j-1] = a[j];
                a[j] = tmp;
            }
        }
    }
}

//方式一，每次insert最大的数到“有序区”的前面。数组前部分为无序区，后部分为有序区。
void bubble_sort2(int a[], int n) {
    int i,j;
    int tmp;
    for (i=0; i<n-1; i++) {
        for (j=0; j<n-1-i; j++) {  //从前往后“下沉”最大的数。
            if (a[j] > a[j+1]) {
                tmp = a[j];
                a[j] = a[j+1];
                a[j+1] = tmp;
            }
        }
    }
}

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

int main() {
    const int N=15;
    int a[N], b[N];
    int i;
    for (i=0; i<N; i++) {
        a[i] = b[i] = rand() % 100;  //这里没加入随机种子，每次都会得到同样的随机数。
    }
    print_array(a, N);   // 输出：7 49 73 58 30 72 44 78 23 9 40 65 92 42 87 

    bubble_sort1(a, N);
    bubble_sort2(b, N);

    print_array(a, N);   // 输出：7 9 23 30 40 42 44 49 58 65 72 73 78 87 92 
    print_array(b, N);   // 输出：7 9 23 30 40 42 44 49 58 65 72 73 78 87 92 
}

void bubble_sort2_optimize(int a[], int n) {
    int i,j;
    int tmp;
    int swapped=0;
    for (i=0; i<n-1; i++) {
        for (j=0; j<n-1-i; j++) {  //从前往后“下沉”最大的数。
            if (a[j] > a[j+1]) {
                tmp = a[j];
                a[j] = a[j+1];
                a[j+1] = tmp;
                swapped = 1;
            }
        }
        if (swapped == 0) { return; }
    }
}

//直接插入排序：每趟把无序区的第一个元素插入到有序区的恰当位置，直到没有无序区。
void insert_sort(int a[], int n) {
    int i,j;
    int flag;
    for (i=1; i<n; i++) {
        flag = a[i];               //把无序区的第一个元素，也就是当前要插入的元素保存到flag中
        for (j = i-1; flag < a[j] && j >= 0; j--) {  //从无序区的前一个位置开始向前寻找插入位置
            a[j+1] = a[j];         //把比flag大的元素后移一位
        }
        a[j+1] = flag;             //找到插入位置，将原a[i]中的值存入第j+1个位置，本次插入完成
    }
}

void insert_sort(int a[], int n) {
    int i,j;
    int flag;
    for (i=1; i<n; i++) {                            /* 外层循环 */
        flag = a[i];
        for (j = i-1; flag < a[j] && j >= 0; j--) {  /* 内层循环 */
            a[j+1] = a[j];
        }
        a[j+1] = flag;
    }
}

//二分插入排序实现（仅当n较大时，性能略优于直接插入排序）
void binary_insert_sort(int a[], int n) {
    int low,high,mid;
    int temp;
    for (int i = 1; i < n; i++)
    {
        low = 0,
        high = i - 1;
        temp = a[i];
        while (low <= high)      //low>high时while循环结束。
        {
            mid = (low + high)/2;
            if (temp < a[mid])   //把<换成<=算法也能得到正确结果，但排序不稳定了。
                high = mid - 1;  //在前半区间进行查找
            else
                low = mid + 1;   //在后半区间进行查找
        } //while循环结束时low==high+1，记录着有序区中a[i]应当插入的位置。

        for (int j = i - 1; j >= low; j--)    //把所有大于a[low]的元素后移一位
        {
            a[j + 1] = a[j];
        }
        a[low] = temp;  //a[high+1] = temp;也正确，将原a[i]中的值存入a[low]，本次插入完成
    }
}

//Shell排序实现：使用Shell建议的增量序列
//程序摘自：《The C Programming Language》第2版3.5节。
void shell_sort(int a[], int n) {
    int gap, i, j, temp;
    for(gap=n/2; gap>0; gap/=2) {     //设定步长
        for(i=gap; i<n; i++) {
            for(j=i-gap; j>=0 && a[j]>a[j+gap]; j-=gap) {  //比较相距gap的元素，逆序互换
                temp=a[j];
                a[j]=a[j+gap];
                a[j+gap]=temp;
            }
        }
    }
}

//Shell排序。增量序列选择的是Knuth推荐的序列。
void shell_sort_knuth(int a[], int n) {
    int h,i,j,temp;
    for(h=1; h<=n/9; h=h*3+1); //这个for循环仅仅是计算h的初值，使其为下列增量序列中小于等于N/9的最大值，所以最后一个分号是必要的。

    /* h = 1, 4, 13, 40, 121, 364... 3*h+1 */
    for(; h>0; h=h/3) {
        for(i=h; i<n; i++) {
            temp=a[i];
            for(j=i-h; j>=0&& a[j]>temp; j-=h) {
                a[j+h]=a[j];
            }
            a[j+h]=temp;
        }
    }
}

//简单选择排序
template<typename T>
void SelectionSort(T a[],int n)
{
  for(int i =0; i < n-1; i++) { // 不必用 i < n（因为到最后一趟时，最后一个元素肯定为最大）

    // 寻找最小元素下标
    int min = i;
    for(int j = i +1; j < n; j++) {
      if(a[j]< a[min]) min =j;
    }

    // 交换a[i]和a[min]
    if(min != i) {
      T tmp = a[min];
      a[min]= a[i];
      a[i]= tmp;
    }
  }
}

// 归并排序C++实现
#include<iostream>
#include<cstdlib>
#include<algorithm>  // std::stable_sort;

#define N 100

//合并过程。
template<typename T>
void Merge(T a[], int low,int mid,int high) {
  int Lpos = low;
  int Rpos = mid +1;
  T * tmp = new T[(high - low +1)];

  int i =0;
  while(Lpos <= mid && Rpos <= high) { //两个序列中取小者复制给tmp。
    tmp[i++] = (a[Lpos]<= a[Rpos]) ? a[Lpos++] : a[Rpos++];
  }

  //上面while循环结束后，能保证前序列、后序列最多有一个为非空，所以后面2个while循环谁先谁后没关系
  while(Lpos <= mid) {                 //若前序列非空，则复制剩余的记录到tmp。
    tmp[i++]= a[Lpos++];
  }

  while(Rpos <= high) {                //若后序列非空，则复制剩余的记录到tmp。
    tmp[i++]= a[Rpos++];
  }

  for(i = low; i <= high; i++) {       //i <= high;必须要等号，因为函数参数传递进来就是数组下标了。
    a[i]= tmp[i-low];                  //把tmp[0..(high - low)]复制给a[low..high]。
  }
  delete[] tmp;
}

template<typename T>
void MSort(T a[],int low,int high) {
  if(low < high) {
    int mid =(low + high)/2;      //分解
    MSort(a,low,mid);             //递归对a[low..mid]排序
    MSort(a,mid+1,high);          //递归对a[mid+1..high]排序
    Merge(a,low,mid,high);        //合并。是Merge<T>(a,low,mid,high);的略写。
  }
}

//归并排序测试代码
int main() {
  int a[N],b[N];

  for(int i=0; i<N; i++) {
    b[i]= a[i]= std::rand()%(5*N); //这里没加入随机种子，每次都是同样随机数。
  }
  std::cout<<"排序前数组为："<< std::endl;
  for(int i=0; i<N; i++) { std::cout<<a[i]<<" ";}

  std::stable_sort(b,b+N); //利用algorithm中的排序算法进行排序。
  std::cout<<std::endl<<"STL算法排序后数组为："<<std::endl;
  for(int i=0; i<N; i++) { std::cout<<b[i]<<" ";}

  MSort<int>(a,0,N-1); //也可是MSort(a,0,N-1);函数模板的实参可省。
  std::cout<<std::endl<<"归并排序排序后数组为："<<std::endl;
  for(int i=0; i<N; i++) { std::cout<<a[i]<<" ";}
  std::cout<<std::endl;
}

// 快速排序实现（Lomuto版本）
#include<iostream>
#include<cstdlib>

#define N 100

void swap(int *x, int *y) {
  int tmp = *x;
  *x = *y;
  *y = tmp;
}

int lomuto_partition(int A[], int l, int h) {
  int pivot = A[h];           /* 假定最后一个元素为枢纽元 */
  int i = l;
  int j;
  for (j=l; j < h; j++) {
    if (A[j] < pivot) {
      swap(&A[i], &A[j]);     /* 如果发现元素比枢纽元小，就把这个小数移动到“大数子数组”的前面
                                 （具体操作是该元素和“大数子数组”的第1个元素） */
      i++;                    /* i中保存着“大数子数组”第1个元素的下标 */
    }
  }

  swap(&A[i], &A[h]);        /* 把枢纽元放入到“小数子数组”和“大数子数组”中间 */
  return i;                  /* 返回枢纽元的下标  */
}

void quicksort(int A[], int l, int h) {
  int p;
  if (l < h) {
    p = lomuto_partition(A, l, h);
    quicksort(A, l, p-1);
    quicksort(A, p+1, h);
  }
}

int main() {
  int a[N];
  for(int i=0; i<N; i++) {
    a[i]= std::rand()%(5*N);   //这里没加入随机种子，每次都是同样随机数。
  }
  std::cout<<"array before sorting:"<<std::endl;
  for(int i=0; i<N; i++) { std::cout<<a[i]<<" "; }

  quicksort(a,0,N-1);

  std::cout<<std::endl<<"array after sorting:"<<std::endl;
  for(int i=0; i<N; i++) { std::cout<<a[i]<<" "; }
  std::cout<<std::endl;
}

/*
  快速选择算法
  返回A中第k大(其中l <= k <= h)的元素，会修改A本身
  比如，要找最小的元素：quickselect(A, 0, N-1, 0)
  要找最大的元素：quickselect(A, 0, N-1, N-1)
*/
int quickselect(int A[], int l, int h, int k) {
  if (l > k || l > h || k > h) {
    throw std::invalid_argument("argument error.");
  }

  if (l == h) {
    return A[l];
  }

  int p = lomuto_partition(A, l, h);
  if (k == p) {           // 已经找到，直接返回
    return A[k];
  } else if (k < p) {     // 去左边找
    return quickselect(A, l, p-1, k);
  } else {                // 去右边找
    return quickselect(A, p+1, h, k);   // 或者 return quickselect(A+p+1, 0, h-(p+1), k-(p+1));
  }
}