要求：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有技术位于数组的前半部分，所有偶数位于数组的后半部分。
思路：
法一：不稳定（类似快速排序）：定义两个指针，指向数组的头部和尾部，head遇到奇数往后移动，tail遇到偶数往前移动， 如果head指向偶数，tail指向奇数，则互换，直到head=tail，退出循环
法二：稳定（插入排序思想）：外层for循环设定指针i从头遍历数组，每次判断i指针所指的值是否为奇数，内层while循环设定j指针往前遍历，将j所指奇数往前移动，直到移动到前方都是奇数的K位置。
public class L22_ReorderOddEven {
// 方法一
public static void ReorderOddEven(int[] list){
// 检查边界
if(list==null || list.length==0){
return;
}
// 定义两个指针，指向数组的头部和尾部
int head=0;
int tail=list.length-1;
// head往后移动，tail往前移动，直到head=tail，退出循环
while(head<tail){
int temp = 0;
// 如果head指向的数为奇数，则head往后移
if(head<tail&&list[head]%2!=0){
head++;
}
// 如果tail指向的数为偶数，则head往前移
if(head<tail&&list[tail]%2==0){
tail--;
}
// 如果head指向偶数，tail指向奇数，则互换
if(list[head]%2==0 && list[tail]%2 !=0){
temp = list[head];
list[head] = list[tail];
list[tail] = temp;
head++;
tail--;
}
}
}
// 方法二
public static void ReorderOddEven1(int[] arr){
// 类似插入排序的方法
if(arr==null||arr.length==0){
return;
}
int k=0; // 用来记录摆好位子的奇数个数
for(int i=0; i<arr.length; i++){
if (arr[i] % 2 == 1) {
int j = i;
while (j > k) {//j >= k+1
// 交换
int tmp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = tmp;
j--;
}
k++;
}
}
}
// 插入排序
public static void InsertSort(int[] arr){
//从第二个位置，即下标为1的元素开始向前插入
for(int i=1; i<arr.length;i++){
// 从第i个元素开始向前比较，如果小于前一个元素，交换位置
for(int j=i; j>0; j--){
if(arr[j]<arr[j-1]){
// 交换
int tmp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = tmp;
}
}
}
}
// 快速排序
public static void quickSort(int[] arr,int left, int right) {
if(left>right){
return;
}
int middle_value = arr[left]; // 先设定一个基准元素
int hight = right;
int low = left;
while(low<hight){
// 顺序很重要，先从右边开始往左找，直到找到比middel值小的数
while(arr[hight]>=middle_value && low<hight){
hight--;
}
// 此时找到了比middle_值小的数，把小的数放到前面
arr[low] = arr[hight];
// # 如果low与high未重合，low指向的元素比基准元素小，则low向右移动
while(arr[low]<middle_value && low<hight){
low++;
}
// 此时找到了比middle_值大的数，把大的数放到后面
arr[hight] = arr[low];
}
// 当退出循环，大于midde_value的在右，小于middLe_value的在左
// 此时low与hight重合
arr[low] = middle_value;
// 把小于基准值元素的子数列和大于基准值元素的子数列排序。
quickSort(arr,left,low-1);
quickSort(arr,low+1,right);
}
public static void main(String[] args) {
int[] arr= {2,4,5,23,1,3};
// InsertSort(arr);
ReorderOddEven1(arr);
for(int i=0; i<arr.length; i++){
System.out.println(arr[i]);
}
}
}
快速排序：
快速排序（英语：Quicksort），又称划分交换排序（partition-exchange sort），通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
步骤为：
1、从数列中挑出一个元素，称为"基准"（pivot），
2、重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
3、递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
最坏时间复杂度：
稳定性：不稳定
插入排序：
插入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
最坏时间复杂度：
稳定性：稳定
网友评论