/*所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。排序算法，就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视，尤其是在大量数据的处理方面。一个优秀的算法可以节省大量的资源。在各个领域中考虑到数据的各种限制和规范，要得到一个符合实际的优秀算法，得经过大量的推理和分析。*/
package cn.hncu.sort;
public class sortMethods {
public static void main(String[] args) {
int[] number={ 21, 25, 49, 25, 16, 8 ,-101,3,50,-5};
// bubble(number);//冒泡算法:
// bubble2(number);//冒泡算法：算法最佳
// select(number);//选择排序
// insert(number);//插入排序
// myInsert(number);复杂的插入排序
//insert2(number);
//shell(number);
// quickSort(number, 0, number.length-1);
mergeSort(number, 0, number.length-1);
print(number);
}
//输出
private static void print(int[] number) {
for(int x:number){
System.out.print(x+"\t");
}
}
//交换
private static void temp(int[] number, int i, int j) {
// number[i]=number[i]+number[j];//利用加法进行交换，仅限于基本数据类型
// number[j]=number[i]-number[j];
// number[i]=number[i]-number[j];
int temp=number[i];//利用第三个变量
number[i]=number[j];
number[j]=temp;
// number[i]^=number[j];//异或,整形
// number[j]^=number[i];
// number[i]^=number[j];
}
//冒泡排序:普通 T(n)=O(n²) S(n)=O(1)
private static void bubble(int[] number) {
for(int i=0;i<number.length-1;i++){
for(int j=i+1;j<number.length;j++){
if(number[i]>number[j]){
temp(number,i,j);
}
}
}
}
//冒泡排序:算法最佳
private static void bubble2(int[] number) {
for(int i=0;i<number.length-1;i++){
boolean flag=true;
for(int j=i+1;j<number.length;j++){
if(number[i]>number[j]){
temp(number,i,j);
flag=false;
}
}
if(flag){
return;
}
}
}
//选择排序 T(n)=O(n²) S(n)=O(1)
private static void select(int[] number) {
for(int i=0;i<number.length-1;i++){
int k=i;//注意
for(int j=i+1;j<number.length;j++){
if(number[k]>number[j]){
k=j;
}
}
if(k!=i){
temp(number, i, k);
}
}
}
//直接插入排序 :直接插入排序是一种稳定的排序方法
//直接插入排序最大的优点是简单，在记录数较少时，是比较好的办法。
private static void insert(int[] number) {//插入排序:不太理解，但是简便
for(int i=0;i<number.length-1;i++){
int temp=number[i+1];
int j=i;
while(number[j]>temp){
number[j+1]=number[j];
if(--j<0){
break;
}
}
number[j+1]=temp;
}
}
//我喜欢用的插入排序算法：但是不简便,而且不好，负载太多交换了很多次多
private static void myInsert(int[] number) {
for(int i=0;i<number.length-1;i++){
for(int j=i;j<number.length;j++){
if(number[i+1]<number[j]){
temp(number, i+1, j);
}
}
}
}
//二分插入排序 ：
//二分查找：找到中间元素，如果中间元素比当前元素大，
//则当前元素要插入到中间元素的左侧；否则，中间元素比当前元素小，则当前元素要插入到中间元素的右侧。
//二分查找优化的插入排序
private static void insert2(int[] number){
for(int i=0;i<number.length-1;i++){
int temp=number[i+1];
int low=0;
int high=i;
int mid;
while(low<=high){
mid=(low+high)/2;
if(number[mid]>temp){
high=mid-1;
}else{
low=mid+1;
}
}
//经过上面的二分查找，得到新元素的位置是：high+1
//把[high+1,i]区间内的所有元素往后移一个位置
for(int j=i;j>high;j--){
number[j+1]=number[j];
}
number[high+1]=temp;
}
}
//希尔排序 ：分组后n值减小，n²更小，而T(n)=O(n²),所以T(n)从总体上看是减小了。
private static void shell(int[] number){
for(int gap=number.length/2;gap>0;){//每次减少gap/2
for(int i=0;i<number.length-gap;i++){//number.length-gap次
for(int j=i;j<number.length-gap;j+=gap){//number.length-gap次换
if(number[j]>number[j+1]){
temp(number, j, j+1);
}
}
}
//for循环的修改代码有点复杂，直接写在for()里面不方便，因此单独拿出来放在这里
if(gap>1){
gap=(gap+1)/2;//防止基数
}else if(gap==1){
break;
}
}
}
//快速排序 最好情况（每次总是选到中间值作枢轴）T(n)=O(nlogn)
//最坏情况（每次总是选到最小或最大元素作枢轴）T(n)=O(n²)
private static void quickSort(int[] number,int p,int r){
if(p<r){
int q=partition(number,p,r);//划分为两部分 a[p:r] ==> a[p:q-1], a[q], a[q+1:r]
quickSort(number, p, q-1);
quickSort(number, q+1, r);
}
}
private static int partition(int[] number, int p, int r) {
int i=p;
int j=r+1;
int x=number[p];//第1个元素为枢轴
while(true){
//在左侧定位到比枢轴大的数
//在右侧定位到比枢轴小的数
while(number[++i]<x&&i<r);
while(number[--j]>x);//这里不要防范，因为一定有一个数等于x
if(i>=j){
break;
}
temp(number, i, j);
}
temp(number, p,j);
return j;
}
//归并排序 T(n)=O(nlogn) S(n)=O(n)
private static void mergeSort(int[] number,int left,int right){
if(left<right){
//1先分解
//把整个数组分解成：[left,mid] 和 [mid+right]
int mid=(left+right)/2;
mergeSort(number, left, mid);
mergeSort(number, mid+1, right);
int[] b=new int[number.length];
merge(number,b,left,mid,right);
copyArray(number,b,left,right);
}
}
private static void copyArray(int[] number, int[] b, int left, int right) {
for(int i=left;i<=right;i++){
number[i]=b[i];
}
}
private static void merge(int[] number, int[] b, int left, int mid, int right) {//注意等于号
int p=left;
int r=mid+1;
int i=left;//游标，遍历合并后结果数组。指定当前判断之后所选中的元素应该放在哪个位置
while(p<=mid&&r<=right){
if(number[p]>number[r]){
b[i++]=number[r++];
}else{
b[i++]=number[p++];
}
}
if(p>mid){
for( int j=r;j<=right;j++){
b[i++]=number[j];
}
}else{
for (int j = p; j <=mid; j++) {
b[i++] = number[j];
}
}
}
}