排序算法的c++实现

#include<iostream>
#include<vector>
using namespace std;

void bubbleSort(vector<int>& nums){
  int size = nums.size();
  for (int p=size-1;p>=0;p--){ //每轮循环将p处元素就位
    int flag = 0;              // 退出标记
    for (int i=0;i<p;i++){     // 访问至p-1处元素
      if(nums[i]>nums[i+1]){   //严格大于，稳定
        swap(nums[i], nums[i+1]);
        flag = 1;
      }
    }
    if (flag==0) break;
  }
  return;
}

void insertionSort(vector<int> &nums){
  int size = nums.size();
  for (int p=1;p<=size-1;p++){
    int tmp = nums[p];
    int i;
    for (i=p;i>0 &&nums[i-1]>tmp ;i--) nums[i] = nums[i-1];
    nums[i] = tmp;
  }
  return;
}

void originalShellSort(vector<int> &nums){
  int size = nums.size();
  for (int D=size/2;D>0;D/=2){
    for (int p=D;p<=size-D;p+=D){
      int tmp = nums[p];
      int i;
      for (i=p;i>=D && nums[i-D]>tmp; i-=D){//i>=D因为插排中的i>0实际上是i>=1
        nums[i] = nums[i-D];
      }
      nums[i] = tmp;
    }
  }
}

//归并排序递归版
void merge(vector<int> &nums, int left, int mid, int right){
  // 优化：不在每次merge处申请tmp，而在最外面统一申请，反复使用
  int* tmp = new int[right-left+1]; //申请新的数组空间
  int p1 = left, p2 = mid, pc = 0;
  while(p1<=mid-1&&p2<=right){
    if (nums[p1]<nums[p2]) tmp[pc++] = nums[p1++];
    else tmp[pc++] = nums[p2++];
  }
  while(p1<=mid-1) tmp[pc++] = nums[p1++];
  while(p2<=right) tmp[pc++] = nums[p2++];
  // 这里倒着把tmp中的元素放入nums中
  for (int i=right-left;i>=0;i--) nums[right--] = tmp[i];
  delete[] tmp;//释放申请的空间
}

void mergeSort1(vector<int> &nums, int left, int right){
  if (left<right){ //left==right时，只有一个元素，返回即可
      int mid = left+(right-left)/2;
      mergeSort1(nums, left, mid);   //此时坐标已经排序好
      mergeSort1(nums, mid+1, right);//此时右边已经排序好
      merge(nums, left, mid+1, right);//合并两个排序好的序列
  }
}

// 归并排序迭代版
void mergeSort2(vector<int> &nums, int left, int right){
  int size = nums.size();


}
// 归并排序总接口
void mergeSort(vector<int>& nums){
  mergeSort1(nums, 0, nums.size()-1);
}

// 快速排序
int median3(vector<int> &nums, int left, int right){
  int mid = left+(right-left)/2;
  if (nums[left]>nums[mid]) swap(nums[left], nums[mid]);
  if (nums[left]>nums[right]) swap(nums[left], nums[right]);
  if (nums[mid]>nums[right]) swap(nums[mid], nums[right]);
  //此时三处元素顺序已经排好
  swap(nums[mid], nums[right-1]);
  return nums[right-1];

}
int partition(vector<int> &nums, int left, int right){
  // cout<<1;
  int pivot = median3(nums, left, right);
  // for (auto num:nums) cout<<num;
  // cout<<endl;
  int p1=left, p2 = right-1;
  while(true){
    // cout<<p1;
    while(nums[++p1]<pivot);
    while(nums[--p2]>pivot);
    if (p1<p2) swap(nums[p1], nums[p2]);
    else break;
  }
  swap(nums[p1],nums[right-1]);
  // cout<<2;
  return p1;
}
void quickSortCore(vector<int> &nums, int left, int right){
  // cout<<left<<right<<endl;
  if (left==right) return; //补丁1
  if (right-left+1>3)
    {int ready = partition(nums, left, right);
    // for (auto num:nums) cout<<num;
    // cout<<endl;
    quickSortCore(nums,left,ready-1);
    quickSortCore(nums,ready+1,right);
    return;}
  //left right区间小的时候，上述代码处理边界有点问题
  else median3(nums,left,right); //补丁2 长度<=3再找中位数就有点问题了
}
void quickSort(vector<int> &nums){
  quickSortCore(nums,0,nums.size()-1);
  return;
}

int main(){
  // 中位数时 2 2 6
  vector<int> nums = {2,4,1,5,6,7,3,2,5,6,8,4,2,5,6};
  vector<int> nums2 = {2,4,1,5,6,7,3,2,5,6,8,4,2,5,6};
  quickSort(nums);
  insertionSort(nums2);
  for (auto num:nums) cout<<num;
  cout<<endl;
  for (auto num:nums2) cout<<num;
  return 0;
}
排序算法的c++实现

相关推荐
