单个有序快排 需要理解 然后改成通用的
1 4 7 8 3 6 9 以8为分界点
// 偶数会出现问题
void merge(int arr[],int length)
{ int i=0;//原数组指针位置
int mid =length/2; //获取排序数组的中间位置
int j=mid+1 ;//中间右边的位置
int* temp =new int[length];//创建和排序数组登场的空数组
int k=0;//新建等长排序数组的指针位置
while (i<=mid && k<=length)
{
/*
if (arr[i]<=arr[j])//加上等号 排序算法稳定
{
temp[k++]=arr[i++];
}
else{
temp[k++]=arr[j++];
}
*/
arr[i]<=arr[j] ? temp[k++]=arr[i++] : temp[k++]=arr[j++];
}
while(i<=mid) //如果其中一个数组已经结束
temp[k++]=arr[i++];
while(j<=length)
temp[k++]=arr[j++];
for (int i=0;i<length;i++)//调试输出
{
printf("%d ",temp[i]);
}
}
快排源码
void MergeArray1(int array[], int start,int mid, int end , int temp[])
{
int i=start;//原始数组最左边指针
int j=mid+1;//分组后右边开始第一个
int k=0;//新数组第一个位置指针
while(i<=mid && j<=end) //原始数组左边小于中间 且 右边的小于 最右边边界
{
if (array[i]<=array[j])
{
temp[k++]=array[i++]; //向数组中复制
}else
{
temp[k++]=array[j++];
}
}
while (i <= mid) {
temp[k++] = array[i++]; //如果左边没有遍历完的情况下 直接复制过来 右边同理
}
while (j <= end) {
temp[k++] = array[j++];
}
//数组拷贝 把temp 复制的arr里面去 但是这个临时数组每次都是从0开始的要注意 平时用不到最大最后一次才会用到最大
for (int i = 0; i < k; i ++) {
array[start + i] = temp[i];
}
}
//递归
void repeatCall(int arr[] ,int start,int end,int temparr[])
{
if (start<end)
{
int mid=start+(end-start)/2; //固定写法
repeatCall(arr,start,mid,temparr);//左递归
repeatCall(arr,mid+1,end,temparr);//右递归
MergeArray1(arr,start,mid,end,temparr);//合并
}
}
int main(int argc, const char * argv[]) {
// int aaa[]={1 ,4 ,7 ,8 ,3 ,6 ,9 ,10};
int array[] = {3,5,3,6,7,3,7,8,1};
int temparr [9]={0};
repeatCall(array,0,9,temparr);
for (int i=0;i<9;i++)
{
printf("%d ",array[i]);
}
return 0;
}