C++ 不知算法系列之从希尔、归并排序算法中的分治哲学聊起

#include <iostream>
using namespace std;
// 插入排序
void insertSort(int nums[],int size, int start,int increment) {
//后指针指向原数列的第 2 个数字,所以索引号从 1 开始
for(int backIdx=start + increment; backIdx<size; backIdx+=increment) {
 // 初始，前指针和后指针的关系，
 int frontIdx = backIdx;
 while(frontIdx>=0 && nums[frontIdx]<nums[frontIdx-increment] ) {
  //交换
  int tmp=nums[frontIdx];
  nums[frontIdx]=nums[frontIdx-increment];
  nums[frontIdx-increment]=tmp;
  }
 }
}
// 希尔排序
void shellSort(int nums[],int size) {
 // 增量
 int increment=size/2;
 // 新数列
 while (increment > 0) {
  // 增量值是多少，则切分的子数列就有多少
  for(int start=0; start<increment; start++) {
   insertSort(nums,size, start, increment);  
  }
  // 修改增量值，直到增量值为 1
  increment = increment / 2;
 }
}
int main(int argc, char** argv) {
 int nums[] = {3, 9, 8, 1, 6, 5, 7};
 int size=sizeof(nums)/4;
 shellSort(nums,size);
 for(int i=0; i<size; i++ ) {
  cout<<nums[i]<<"\t";
 }
 return 0;
}

#include <iostream>
using namespace std;
// 切分原数列
void splitNums(int nums[],int start,int end ) {
 int size=end-start;
 for(int i=start; i<size+start; i++)
  cout<<nums[i]<<"\t";
 cout<<endl;
 if (size>1)  {
  // 切分线，中间位置
  int spLine = size / 2;
  splitNums(nums,start,spLine+start);
  splitNums(nums,spLine+start,end );
 }
}
int main(int argc, char** argv) {
 int  nums[] = {3, 9, 8, 1, 6, 5, 7};
 int size=sizeof(nums)/4;
 splitNums(nums,0,size);
 return 0;
}

#include <iostream>
using namespace std;
int  nums_[] = {3, 9, 8, 1, 6, 5, 7};
// 切分原数列
void splitNums(int nums[],int start,int end ) {
 int size=end-start;
 if (size>1)  {
  // 切分线，中间位置
  int spLine = size / 2;
  //前子数组的绝对大小
  int s1=spLine;
  //后子数组的绝对大小
  int s2=end-spLine-start;
  //前面的子数组
  int nums01[s1];
  int idx=0;
  //切分原数组,注意相对位置
  for(int i=start; i<spLine+start; i++) {
   nums01[idx]=nums_[i];
   idx++;
  }
  int nums02[s2];
  idx=0;
  for(int i=spLine+start; i<end; i++) {
   nums02[idx]=nums_[i];
   idx++;
  }
  splitNums(nums01,start,spLine+start);
  splitNums(nums02,spLine+start,end );
  // 为 2 个数列创建 2 个指针
  int idx_01 = 0;
  int  idx_02 = 0;
  int k = 0;
  while (idx_01 < s1 and idx_02 < s2 ) {
   if (nums01[idx_01] > nums02[idx_02]) {
    // 合并后的数字要保存到原数列中
    nums[k] = nums02[idx_02];
    idx_02 += 1;
   } else {
    nums[k] = nums01[idx_01];
    idx_01 += 1;
   }
   k += 1;
  }
  // 检查是否全部合并
  while (idx_02 < s2) {
   nums[k] = nums02[idx_02];
   idx_02 += 1;
   k += 1 ;
  }
  while (idx_01 < s1) {
   nums[k] = nums01[idx_01];
   idx_01 += 1;
   k += 1;
  }
 }
}
int main(int argc, char** argv) {
 int size=sizeof(nums_)/4;
 splitNums(nums_,0,size);
 cout<<"归交排序："<<endl;
 for(int i=0;i<size;i++ ){
  cout<<nums_[i]<<"\t";
 }
 return 0;
}

#include <iostream>
using namespace std;
int main(int argc, char** argv) {
 // 原数列
 int nums[] = {3, 9, 8, 1, 6, 5, 7};
 int size=sizeof(nums)/4;
 // 找到数列中的最大值
 int maxVal=nums[0];
 for(int i=1; i<size; i++) {
  if( nums[i]>maxVal )
   maxVal=nums[i];
 }
 int sortNums[maxVal+1]= {0};
 for (int i : nums) {
  sortNums[i]=i;
 }
 for (int i : sortNums) {
  if(i!=0)
   cout<<i<<"\t";
 }
 return 0;
}

#include <iostream>
#include <cmath>
using namespace std;
//排序用数组
int sortNums[10][10]= {0};
void baseSort(int nums[],int size,int start,int depth) {
 if(start==depth) {
  return;
 }
 //取位
 for(int i=0; i<size; i++) {
  int wei=pow(10,start);
  int temp=nums[i] / wei %  10;
  for(int j=0; j<10; j++) {
   if( sortNums[temp][j]==0 ) {
    sortNums[temp][j]=nums[i] ;
    break;
   }
  }
 }
 //取出排序的数据
 int idx=0;
 for(int row=0; row<10; row++) {
  for(int col=0; col<10; col++) {
   if( sortNums[row][col]!=0 ) {
    nums[idx]=sortNums[row][col];
    sortNums[row][col]=0;
    idx++;
   }
  }
 }
 //递归
 baseSort(nums,size,start+1,depth);
}
int main(int argc, char** argv) {
 // 原数列
 int nums[] = {1, 98, 51, 2, 32, 114, 99, 13, 45};
 int size=sizeof(nums)/4;
 int bakNums[size];
 for(int i=0; i<size; i++) {
  bakNums[i]=nums[i];
 }
 //找到最大值
 int maxVal=nums[0];
 for(int i=1; i<size; i++) {
  if(nums[i]>maxVal) {
   maxVal=nums[i];
  }
 }
 //计算最大值的位数
 string str= to_string(maxVal);
 int depth=str.size();
 //基数排序
 baseSort(nums,size,0,depth);
 for(int i=0; i<size; i++) {
  cout<<nums[i]<<"\t";
 }
 return 0;
}