C语言中常见的排序算法(冒泡、选择、堆排、插入、归并)以及效率测试

发布于 / C语言 / Comments Off on C语言中常见的排序算法(冒泡、选择、堆排、插入、归并)以及效率测试

0、一个非常舒服的视频(来源见水印)

1、冒泡排序

void Bubble_Sort(ElementType A[], int N){
    for(int P = N-1; P >= 0; P--){ 
    //每轮排序后,末尾的数字一定是最大的,所以下一轮排序无需遍历到末尾
        for(int i = 0; i < P; i++){ 
        //一轮排序中遍历所有的数字
            if(A[i] > A[i+1])    //如果顺序是错误的
                swap(A[i], A[i + 1])
                //交换
        }
    }
}

2、冒泡排序(改进版)

void Bubble_Sort(ElementType A[], int N){
    for(int P = N-1; P >= 0; P--){ 
        bool flag = false; //标记
    //每轮排序后,末尾的数字一定是最大的,所以下一轮排序无需遍历到末尾
        for(int i = 0; i < P; i++){ 
        //一轮排序中遍历所有的数字
            if(A[i] > A[i+1]){    //如果顺序是错误的
                swap(A[i], A[i + 1])
                //交换
                flag = true //这一轮中执行了交换操作
            }
        }
        if(flag == false) break;
        //如果本轮操作没有执行交换位置的操作,说明已经是顺序了,跳出循环即可
    }
}

3、选择排序

void Selection_Sort(){
    for(int i = 0; i < N; i++){
        int MinPosition, min = inf;
        //inf是一个很大的数字
        for(int j = i; j < N; j++)
            if(A[j] < min) min = A[j], MinPosition = j;
        //上面这个循环的目的是找到i以后的最小元
        swap(A[i], A[MinPosition]);    //交换位置
    }
}

4、堆排序

//非递归写法
void DownAdjust(int low, int high){
  int i = low, j = i * 2;  //i存放要调整的节点,j存放其左孩子 
  while(j <= high){  //j没越界,说明存在孩子节点 
    if(j+1 <= high){  //防止不存在右孩子而导致越界 
      if(heap[j + 1] > heap[j]) //右孩子更大
        j = j + 1;  //让j存放右孩子的下标 
    }
    //如果孩子中最大的值比欲调整节点i大 
    if(heap[j] > heap[i]){
      swap(heap[j], heap[i]);//交换最大的孩子与要调整的节点i 
      i = j;  //保持i为要调整的节点
      j = i * 2;  //j为i的左孩子  
    }else
      break;  //孩子都比要调整的i小,调整结束 
  }
}
//递归写法
void DownAdjust(int low, int high){
  int i = low, j = i * 2;  //i是要调整的节点,j是左孩子 
  if(j > high) return;  //如果没有左孩子(越界),直接返回 
  int max_index = heap[i] > heap[j] ? i : j;  //在左孩子与要调整的节点中找到最大的下标
  //如果存在右孩子,在刚刚找到的最大的下标和右孩子中找最大的 
  if(j + 1 < high) max_index = heap[max_index] > heap[j + 1] ? max_index : (j + 1);
  if(max_index == i) return;  //如果要调整的节点已经是最大的了,直接返回 
  swap(heap[i], heap[max_index]);  //执行交换 
  DownAdjust(max_index, high);  //递归调整 
}
//建堆
void CreateHeap(){
  for(int i = n / 2; i >= 1; i--)
    DownAdjust(i, n);
} 
//排序函数
void HeapSort(){
  CreateHeap();
  for(int i = n; i > 1; i--){
    swap(heap[i], heap[1]);
    DownAdjust(1, i - 1);
  }
}


5、插入排序

void Insertion_Sort(int a[], int n){
    for(int i = 1; i < n; i++){
        //越过0,从1开始遍历
        for(int j = i; j >= 1; j--){
            //从i往前遍历
            if(a[j] < a[j-1])    //如果比前一个小
                swap(a[j], a[j-1]);    //则与前一个交换顺序
            else break;    //否则跳过这一轮(因为从1开始遍历,保证i前面是有序的)
        }
    }
}


6、归并排序

void Merge(int frist, int mid, int last){  //合并数组到ans数组中 
  int tmp[N];    //临时数组 
  int p1 = frist, p2 = mid + 1;  //两组数的位置
  int p1_max = mid, p2_max = last;  //最大位置(位置与最大位置比较,防止越界) 
  int k = 0;  //临时数组位置 
  while(p1 <= p1_max && p2 <= p2_max){  //在范围内 
    if(arr[p1] < arr[p2])  //当前左边的数比右边的小 
      tmp[k++] = arr[p1++];  //将p1位置的数字拷贝过去,并移动一位
    else tmp[k++] = arr[p2++] ;
  }
  //完成后,将剩下的数据直接拷贝到ans中
  while(p1 <= p1_max)
    tmp[k++] = arr[p1++];
  while(p2 <= p2_max)
    tmp[k++] = arr[p2++];
  //将临时数组中的结果拷贝回去,注意下面的i是偏移量,必须加上frist 
  for(int i = 0; i < k; i++)
    arr[frist + i] = tmp[i];
} 

void MergeSort(int frist, int last){
  if(frist >= last) return;  //frist >= last的时候到达递归终点 
  int mid = (frist + last) / 2;  //计算中间下标
  MergeSort(frist, mid);          //通过递归,将中心以左的序列 [frist, mid] 进行归并排序 
  MergeSort(mid + 1, last);  //通过递归,将中心以右的序列 [mid + 1, last] 进行归并排序
  Merge(frist, mid, last);  //合并两组有序数组 
}

7、快速排序

void QuickSort(int arr[], int left, int right){
  if(left >= right) return;  //排序终点 
  int basic = arr[left];  //基数
  int i = left, j = right;  //左右哨兵
  while(i < j){    //如果i>j说明已经全部遍历过了 
    while(arr[j] >= basic && i < j) j--;  //只要大于基数,就--,直到到从右往左第一个小于基数的位置
    while(arr[i] <= basic && i < j) i++;  //只要小于基数,就++,直到到从左往右第一个大于基数的位置
    if(i < j)    //如果i>j说明已经全部遍历过了 
      swap(arr[i], arr[j]); 
  }
  arr[left] = arr[i];  //将中间的数字与基数交换
  arr[i] = basic;    //将基数归位
  QuickSort(arr, left, i - 1);  //左边的递归排序
  QuickSort(arr, i + 1, right);//右边的递归排序 
}

写到这,让我们来做一次算法比较吧!

测试代码(省略了排序函数部分):

#define N 25000
int ori[N], arr[N];  //ori存放原始随机数据,arr存放排序数据,防止排序后污染原始数据 

void init(){  //初始化 
  srand(time(0));
  for(int i = 0; i < N; i++)
    ori[i] = rand() % 1000 + 1;
}

void copy(){  //拷贝原始数据到排序数组  
  for(int i = 0; i < N; i++)
    arr[i] = ori[i];
}

int main(){
  clock_t start, end;
  init();
  //归并排序 
  copy();
  start = clock(); 
  MergeSort(0, N - 1);
  end = clock();
  printf("归并排序%d个随机数据用时%d毫秒\n", N, end - start);
  //冒泡排序
  copy();
  start = clock(); 
  BubbleSort();
  end = clock();
  printf("冒泡排序%d个随机数据用时%d毫秒\n", N, end - start);
  //改进冒泡排序
  copy();
  start = clock(); 
  BubbleSort2();
  end = clock();
  printf("改进版冒泡排序%d个随机数据用时%d毫秒\n", N, end - start);
  //选择排序
  copy();
  start = clock(); 
  SelectionSort();
  end = clock();
  printf("选择排序%d个随机数据用时%d毫秒\n", N, end - start);
  //插入排序
  copy();
  start = clock(); 
  InsertionSort();
  end = clock();
  printf("插入排序%d个随机数据用时%d毫秒\n", N, end - start);
  //堆排序
  copy();
  start = clock(); 
  HeapSort();
  end = clock();
  printf("堆排序%d个随机数据用时%d毫秒\n", N, end - start);
  //std:sort
  copy();
  start = clock(); 
  sort(arr, arr + N);
  end = clock();
  printf("std:sort排序%d个随机数据用时%d毫秒\n", N, end - start);
  //std:stable_sort
  copy();
  start = clock();
  stable_sort(arr, arr + N);
  end = clock();
  printf("std:stable_sort排序%d个随机数据用时%d毫秒\n", N, end - start);
  //Print(); 
  return 0; 
}

运行结果:

捕获.JPG

嗯?好像有几个排序的速度区分不出来,让我们来加一个数量级,重复实验

捕获.JPG

这次的实验结果就很清晰了。

排序算法只是用来学习排序的各种思想,在算法竞赛或者OJ考试中,最好不要重复造轮子,使用sort或者stable_sort进行排序。

转载原创文章请注明,转载自: 斐斐のBlog » C语言中常见的排序算法(冒泡、选择、堆排、插入、归并)以及效率测试
评论已关闭