小挑战

本小节与大家分享一些适合启发新手学习算法的小题目，希望能启发你的斗志！

题目1

你可以使用选择排序给指定整数数组排序吗？

题目2

你可以使用冒泡排序给指定整数数组排序吗？

题目3

你可以使用插入排序给指定整数数组排序吗？

题目4

你可以使用归并排序给指定整数数组排序吗？

题目5

你可以使用快速排序给指定整数数组排序吗？

。。。。。。。。。。。。。我是优美的分割线。。。。。。。。。。。。。

题目1

你可以使用选择排序给指定整数数组排序吗？

public static void selectorSort(int[] array){
    if(array==null|| array.length<2){
	return;
    }
    int len = array.length;
    for(int i=0; i<len; i++){
       int minIndex = i;
       for(int j=i+1; j<len; j++){
        if(array[j]<array[minIndex]){
           minIndex=j;
        }       
       }
       swap(array,i,minIndex);
    }

}

public static void swap(int[] array,int i1,int i2){
    int tmp = array[i1];
     array[i1] = array[i2];
     array[i2] = tmp;
}

思路：

每一次内存循环找到最小值的下标，内存循环结束交换位置；一直到全部执行完毕
第1轮 从下标0开始，结束后找到的最小值下标，与0下标为数字交换位置
第2轮 从下标1开始，结束后找到的最小值下标，与1下标为数字交换位置
第i轮 从下标i-1开始，结束后找到最小值下标，与i-1下标为数字交换位置
.....

题目2

你可以使用冒泡排序给指定整数数组排序吗？

public static void popSort(int[] array){
    if(array==null|| array.length<2){
	return;
    }
    int len = array.length;
    for(int i=len-1; i>=0; i--){
       for(int j=1; j<=i; j++){
          if(array[j-1]>array[j]){
             swap(array,j-1,j);
          }
       }       
    }

}

public static void swap(int[] array,int i1,int i2){
    int tmp = array[i1];
     array[i1] = array[i2];
     array[i2] = tmp;
}

思路：

两两比较，大的往后移动;
第1轮结束后的最大值处于N-1的位置
第2轮结束后的最大值处于N-2的位置
第i轮结束后的最大值处于N-i的位置
.....

题目3

你可以使用插入排序给指定整数数组排序吗？

public static void insertSort(int[] array){
    if(array==null|| array.length<2){
	return;
    }
    int len = array.length;
    for(int i=0; i<len; i++){
       for (int j = i; j > 0 && array[j - 1] > array[j]; j--) {
             swap(array,j-1,j);
          }
       }       
    }

}

public static void swap(int[] array,int i1,int i2){
    int tmp = array[i1];
     array[i1] = array[i2];
     array[i2] = tmp;
}

思路：

构建局部有序;
第1轮结束[0,1]的区间有序
第1轮结束[0,2]的区间有序
第i轮结束[0,i]的区间有序
.....

题目4

你可以使用归并排序给指定整数数组排序吗？

参考题解：递归解法


public static void mergeSort(int[] array){
     if( array==null || array.length<2 ){
	return;
     }
     process(array, 0, array.length-1);
}

public static void process(int[] array,int l,int r){
    if(l >= r){
      return;
    }
    int mid = l+ ((r-l)>>1);
    process(array, l, mid);
    process(array, mid+1, r);
    merge(array, l, mid, r);
}

public static void merge(int[] array,int l,int m,int r){
  int [] help = new int[r-l];
  int i = 0;
  int l1 = l;
  int l2 = m+1;
  while(l1<=m&& l2<=r){
   help[i++] = array[l1]<=array[l2]?array[l1++]:array[l2++];
  }
  
  while(l<=m){
   help[i++] = array[l1++];
  }

  while(l2<=r){
   help[i++] = array[l2++];
  }

  for(i=0;i<help.length;i++){
    array[l+i] =help[i];
  }
}

题目5

你可以使用快速排序给指定整数数组排序吗？

参考题解: 递归解法


public static void quickSort(int[] array){
     if( array==null || array.length<2 ){
	return;
     }
     process(array, 0, array.length-1);
}

public static void process(int[] array,int l,int r){
    if(l >= r){
      return;
    }
    int[] partition = partition(array, l, r);
    process(array, l, partition[0]);
    process(array, partition[1], r);    
}

public static int[] partition(int[] array, int l, int r){
    int less = l-1;
    int more = r;
    int index = l;
    while(index < more){
       if(array[index] < array[r]){
          swap(array, ++less, index++);
       }else if(array[index] > array[r]){
          swap(array, --more, index);
       }else {
         index++;
       }
    }
    swap(array,index,r);
    return new int[]{less,more};
}

public static void swap(int[] array, int i1, int i2){
    int tmp = array[i1];
    array[i1] = array[i2];
    array[i2] = tmp;
}