无锡 电子商务网站建设,图片分享网站源码,ide wordpress,租凭境外服务器做违规网站快速排序
1#xff1a;快速排序的思想 快速排序运用了分治的思想#xff0c;即通过一趟排序 将序列分为两部分#xff0c;根据选取的基准#xff0c; 将比基准小的数放在基准前面#xff0c;将比基准大的数放在的数放在基准后面#xff1b;然后对两部分进行递归处理快速排序的思想 快速排序运用了分治的思想即通过一趟排序 将序列分为两部分根据选取的基准 将比基准小的数放在基准前面将比基准大的数放在的数放在基准后面然后对两部分进行递归处理以达到整个序列有序的状态。
2快速排序的步骤 1选择基准 在一个待排序列中找一个 待排的数作为基准 2分割操作 根据基准将序列分为两部分 3将分割后的序列进行递归操作
3选择基准的方法
1固定基准即选取序列的第一个数或最后一个数作为基准耗费时间长
2三数取中即将序列中的首 中 尾 三个数 取出来 进行比较取 中间那个数
4运算最快的代码组合之一 三数取中 插排
#includestdio.hvoid swap(int a, int b){int temp;temp a;a b;b temp;
}//插入排序
void Insertion_sort(int A[], int low, int high){int P,i; int N high - low;for(P 1; P N; P){int temp A[P];for(i P; i 0 A[i-1] temp; i--){A[i] A[i-1];A[i-1] temp; }}
}
//选取 一个基准 进行 分成两部分 //使用三数取中法选择枢轴
//int getstandard(int A[], int i, int j){
//
// int mid i ((j - i) 1);//计算数组中间的元素的下标
//
// //使用三数取中法选择枢轴
// if (A[mid] A[j])//目标: arr[mid] arr[high]
// {
// swap(A[mid],A[j]);
// }
// if (A[i] A[j])//目标: arr[low] arr[high]
// {
// swap(A[i],A[j]);
// }
// if (A[j] A[i]) //目标: arr[low] arr[mid]
// {
// swap(A[mid],A[i]);
// }
// //此时arr[mid] arr[low] arr[high]
// int key A[i];
// //low的位置上保存这三个位置中间的值
// //分割时可以直接使用low位置的元素作为枢轴而不用改变分割函数了
//
// while(i j){
//
// while(i j A[j] key){
// j--;
// }
// if(i j A[j] key){
// A[i] A[j];
// }
//
// while(i j A[i] key){
// i;
// }
// if(i j A[i] key){ //前面的数如果大于key的话 就将前面的数放到后面?
// A[j] A[i];
// }
// }
// //出这个循环
// A[i] key;
// return i ;
//}//此为选取第一个 数据作为基准
int getstandard(int A[], int left, int right){int i left,j right;int key A[left];//选取 第一个数据为基准while(i j){while(i j A[j] key){j--;} while(i j A[i] key){i;}//当发现 从右边开始发现有比基准数小的时候从左边开始 遇到比基准数大的时候//交换两个数 if(i j){swap(A[i],A[j]);}} //出这个循环 交换基准数 和 i 与 j 相等时那个位置的数 A[left] A[i];A[i] key;return i;
}void QuickSort(int A[] ,int low ,int high){if(low high){int standard getstandard(A, low, high);//递归两部分 QuickSort(A, low, standard-1);QuickSort(A, standard1, high); }//当数据小于10的时候选择插入排序明显 比 快排速度更快 if(high - low 10)Insertion_sort(A, low, high);
}
int main(){int i,n;scanf(%d,n);int a[n];for(i0; in; i){scanf(%d,a[i]);}QuickSort(a,0,n-1);for(i0; in; i){printf(%d ,a[i]);}
}
