By Leo_璇哥

更新日期:

文章目录

排序算法总结

插入排序n2 快速排序nlog2n 不稳 希尔排序 n1.3 不稳
选择排序n2不稳 堆排序nlog2n 不稳 基数排序O(d(n+1))
冒泡排序n2 归并排序nlog2n

冒泡排序

1
void BubbleSort(int a[],int n)
{
 int i,j;
 for(i=0;i<n;i++)
  for(j=1;j<n-i;j++)
   if(a[j-1]>a[j])
    Swap(a[j-1],a[j]);
}

快速排序

1
#include<cstdio>
#include<ctime>
#include<cstdlib>
void Swap(int& a,int& b){if(a!=b){a^=b;b^=a;a^=b
int Partition(int *A,int p,int r)
{
 int x,i;
 x=A[r];
 i=p-1;
 for(int j=p;j<=r-1;++j)
 {
  if(A[j]<=x)
   Swap(A[++i],A[j]);
  //x为最后一个数，小于x，不动（交换）本身（未有大于x的）
  //已有大于x的时，再遇小于x：交换
 }
 Swap(A[++i],A[r]);
 return i;
}
void QuickSort(int *A,int p,int r)
{
 if(p<r)
 {
  int q = Partition(A,p,r);
  QuickSort(A,p,q-1);
  QuickSort(A,q+1,r);
 }
}

堆排序

1
#include<cstdio>
#include<algorithm>
using namespace std;
//《算法导论》堆排序采用最大堆，最小堆通常用于构造最小优先队列
inline int Parent(int i){return i>>1;}
inline int Left(int i){return i<<1;}
inline int Right(int i){return (i<<1) | 1; }
inline void Swap(int &a,int &b){if(a!=b) {a^=b;b^=a;a^=b;}}
//保持堆的性质
void MAXHeap(int *A,int heap_size,int i)
{
 int l,r,max;
 l = left(i);
 r = Right(i);
 if(l<=heap_size && A[l]>A[j])
  max = l;
 else max = i;
 if(r<=heap_size && A[r]>A[max])
  max = r;
 if(max!=i)
 {
  Swap(A[i],A[max]);//就地排序
  MAXHeap(A,heap_size,max);
 }
}
建堆
void BuildMAXHeap(int* A,int heap_size)
{
 for(int i = heap_size>>1;i>=1;--i)
  MAXHeap(A,heap_size,i);
}
排序
void HeapSort(int* A,int heap_size)
{
 BuildMAXHeap(A,heap_size);
 int len = heap_size;
 for(int i=heap_size;i>=2;--j)
 {
  Swap(A[1],A[i]);
  --len;
  MAXHeap(A,len,1);
 }
}

归并排序

1
//归并排序 O(nlog2n) 附加空间O(n)
#include<stdio.h>
#define true 1
#define false 0
void mergearray(int a[],int first,int mid,int last,int temp[])
{
 int i = first,j = mid+1;
 int m = mid,n = last;
 int k = 0;
 while(i<=m && j<=n)
 {
  if(a[i]<a[j])
   temp[k++] = a[i++];
  else temp[k++] = a[j++];
 }
 while(i<m)
  temp[k++] = a[i++];
 while(j<n)
  temp[k++] = a[j++];
 for(i=0;i<k;i++)
  a[first] = temp[i];
}
void mergesort(int a[],int first,int last,int temp[])
{
 if(first<last)
 {
  int mid = (first+last)/2;
  mergesort(a,first,mid,temp);
  mergesort(a,mid+1,last,temp);
  mergearray(a,first,mid,last,temp);
 }
}
int MergeSort(int a[],int n)
{
 int* p = (int*)malloc(n*sizeof(int));//共用临时数组
 if(p == NLL)//内存分配不成功，申请空间是否成功。
  return false;
 mergesort(a,0,n-1,p
 free(p);
 return true;
}
int main()
{
 int i;
 int a[] = {23,4,9,34,12,3,89,7,80};
 MergeSort(a,q);
 for(i=0;i<q;i++)
  printf("%d",a[i]);
  printf("\n");
 return 0;
}

希尔排序

1
希尔排序：插入排序的改进。递减增量排序算法。
步长为1时就是插入排序。
#include<stdio.h>
void ShellSort(int a[],int n)
{
 int i,j,k,temp,gap;
 int gaps[]={1,5,13,43,113,297,815,1989,4711,11969,27901,84801,213331};
 for(k=0;gap[k]<n;k++)
 while(--k>=0)
 {
  gap = gaps[k];
  for(i=gap;i<n;i++)
  {
   j=i-gap;
   temp=a[i];
   while((j>=0)&&(a[j]>temp))
   {
    a[j+gap] = a[j];
    j=j-gap;
   }
   a[j+gap] = temp;
  }
 }
}
或者：
void shellSort(int* data,size_t size)
{
 for(int gap = size/2;gap>0;gap/=2)
  for(int i=gap;i<size;++i)
  {
   int key = data[i];
   int j=0;
   for(j=i-gap;j>=0&&data[j]>key;j-=gap)
   {
    data[j+gap] = data[j];
   }
   data[j+gap] = key;
  }
}
文章目录