Cacher is the code snippet organizer for pro developers

冒泡排序

# A[1...n]
# 从小到大排序
# 稳定、原地

void bubbleSort(int A[], int n)
{
  # 冒n-1轮泡泡
  for(int i=0; i<n-1; i++)
  {
    for(int j=1; j<n-i; j++)
    {
      if(a[j] > a[j+1]) // 如果条件改成A[i] >= A[i + 1],则变为不稳定的排序算法
      {
        swap(a[j], a[j+1])
      }
    }
  }
}

鸡尾酒排序

void cockTailSort(int A[], int n)
{
  int left = 1;
  int right = n;
  while(left < right)
  {
    for(int i=left; i<right; i++)
    {
      if(A[i] > A[i+1])
      {
        swap(A[i], A[i+1])
      }
    }
    right--;
    
    for(int i=right; i>left; i--)
    {
      if(A[i-1] > A[i])
      {
        swap(A[i-1], A[i])
      }
    }
    left++
  }
}

选择排序

# 选择排序是不稳定的排序算法，不稳定发生在最小元素与A[i]交换的时刻。
# 比如序列：{ 5, 8, 5, 2, 9 }
# 一次选择的最小元素是2，然后把2和第一个5进行交换，从而改变了两个元素5的相对次序

void selectionSort(int A[], int n)
{
  for(int i=1; i<n; i++) # i为已排序列的末尾
  {
    min = i
    for(int j=i+1;j<=n; j++)
    {
      if(a[j] < a[min])
      {
        min = j
      }
    }
    if(min != i){
      swap(A[i], a[min])
    }
  }
}

插入排序

# 稳定

void insertionSort(int A[], int n)
{
  for(int k=2; k<=n; k++)
  {
    int get = a[k];
    int j = k-1;
    while(j>=1 && A[j]>get)
    {
      A[j+1]=A[j];
      j--;
    }
    A[j+1] = get;
  }
}

基于二分查找的插入排序

如果比较的代价较高，可以减少比较次数

# 稳定

void insertionSortBinary(int A[], int n)
{
  for(int i=2; i<=n; i++)
  {
    int left = 1;
    int right = i-1;
    int get = a[i];
    
    while(left<=right)
    {
      int mid = (left+right)/2;
      if(get < A[mid])
      {
        right = mid - 1;
      }
      else
      {
        left = mid + 1;
      }
    }
    
    for(int j=i-1; j>=left;j--){
      A[j+1] = A[j];
    }
    
    A[left] = get;
  }
}

归并排序

void mergeSortRecursion(int A[], int left, int right)
{
  if(left == right)
  {
    return;
  }
  int middle = (left+right)/2;
  mergeSortRecursion(A, left, middle);
  mergeSortRecursion(A, middle+1, right);
  merge(A, left, right, middle);
}

void merge(int A[], int left, int right, int middle)
{
  int len = right-left+1;
  int *tmp = new int[len];
  int index = 1;
  int left1 = left;
  int left2 = middle + 1;
  while(left1<=middle && left2<=right)
  {
    if(A[left1]<=A[left2])
    {
      tmp[index++]=A[left1++];
    }
    else
    {
      tmp[index++]=A[left2++];
    }
  }
  while(left1<=middle)
  {
    tmp[index++]=A[left1++];
  }
  while(left2<=right)
  {
    tmp[index++]=A[left2++];
  }
  
  for(int k=1; k<=len; k++)
  {
    A[left++] = tmp[k];
  }
}

堆排序

# 不稳定

void heapify(int A[], int i, int size) //从A[i]向下进行堆调整
{
  int leftChild = i*2;
  int rightChild = i*2 + 1;
  int max = i;

  if (leftChild <= size && A[leftChild] > A[max])
  {
    max = leftChild;
  }
  if (rightChild <=size && A[rightChild] > A[max])
  {
    max = rightChild;
  }
  
  if(max != i)
  {
    swap(A, i, max)
    Heapify(A, max, size)
  }
}

void buildHeadp(int A[], int size)
{
  for(int i=size/2; i>=1; i--)
  {
    heapify(A, i, size);
  }
}

void heapSort(int A[], int n)
{
  buildHeap(A, n);
  
  while(n>1)
  {
    swap(A, 1, n);
    n--;
    heapify(A, 1, n);
  }
}

快速排序

void quickSort(int A[], int left, int right)
{
  if(left == right)
  {
    return;
  }
  
  int pivot_index = partition(A, left, right)
  quickSort(A, left, pivot_index-1);
  quickSort(A, pivot_index+1, right);
}

int partition(int A[], int left, int right)
{
  int pivot = A[right];
  int pivot_index = left - 1;
  for(int i=left; i < right; i++)
  {
    if(A[i]<= pivot)
    {
      pivot_index++;
      swap(A, i, pivote_indeX);
      
    }
  }
  pivote_index++;
  swap(A, right, pivote_index)
  return pivote_index;
}