题目

解题思路

一（选择排序）

• 选择排序为什么叫选择排序呢?他的原理就是选择当前的元素依次和后面的元素进行比较，在第一次比较之后就会将我们想要的结果放在首位，然后接着从第二个元素开始依次和后面的元素进行比较。假如说有8个元素，那么试想一下我们到底应该比几轮？答案是7轮,为什么呢？因为我们第一轮比较完已经将我们要的一个数放在了数组的最左边，再一个就是第8轮也就是最后一个元素后面已经没有值了，那么就不用比了。

用选择排序解这道题的代码

class Solution {
    public int[] sortArrayByParity(int[] A) {
        if(A==null||A.length==1){
            return A;
        }
        //选择排序
        int temp=0;
        /*
        注意，外层循环控制轮数也参与计算
        */
        for(int i=0;i<A.length-1;i++){//最后一轮由于前面已经排好而且最后一轮后面已经没值了，
            //所以只需要比A.length-1轮
            for(int j=i+1;j<A.length;j++){
                if(A[i]%2==1&&A[j]%2==0){//前奇数后偶数，就交换
                    temp=A[i];
                    A[i]=A[j];
                    A[j]=temp;
                }
            }
        }
        return A;
    }
}

算法效率

是真的慢。。。。。。

二（冒泡排序）

• 冒泡排序，就是两两相比，类似于鱼吐泡泡那种，和选择排序不同的是，冒牌排序第一轮排完就将我们要的其中一个值放到了最后，也就是数组的尾部。和选择相同的是冒泡排序也是少比一轮。而且冒泡排序每轮比完都会得出一个结果并将这个结果放在最右边，所以下一轮比的次数总是会比上一轮少一次。

用冒泡排序解这道题的代码

class Solution {
    public int[] sortArrayByParity(int[] A) {
        if(A==null||A.length==1){
            return A;
        }
        //冒泡排序
        //每次都从0开始比，
        int temp=0;
        for(int i=0;i<A.length-1;i++){//最后一轮没有比较的了，所以少比一轮。
            //i只控制轮数，不参与运算
            for(int j=0;j<A.length-1-i;j++){//j参与运算
                if(A[j]%2==1&&A[j+1]%2==0){//前奇数后偶数
                    temp=A[j+1];
                    A[j+1]=A[j];
                    A[j]=temp;
                }
            }      
        }
        return A;
    }
}

算法效率

呵呵呵，更慢。。。。。。

三（插入排序）

代码实现

class Solution {
    public int[] sortArrayByParity(int[] A) {
        if(A==null||A.length==1){
            return A;
        }
        //插入排序
        for(int i=1;i<A.length;i++){
            int e=A[i];
            int j;
            for(j=i;j-1>=0&&A[j-1]%2==1&&e%2==0;j--){
                A[j]=A[j-1];
            }
            A[j]=e;
        }
        return A;
    }
}

可以看出，这三大基本排序，插入排序的效率最高。

用插入排序排大小C语言实现

#include<stdio.h>
//插入排序
/*
第一个元素跳过
从第二个元素开始i
    j从i开始

    1.左边j-1有元素没 j-1>=0 否则 i++
    2.左边j-1是否比j对应的值大 否则 i++
        交换 j--重复1

*/
void main(){
    int a[]={3,1,2,6,5,9,7,4,8};
    int len=sizeof(a)/sizeof(int);

    for(int i=1;i<len;i++){
        int e=a[i];
        int j;
        for(j=i;j-1>=0&&a[j-1]>e;j--){
            // if(j-1<0){//j左边的牌 没有 j-1<0
            //     break;
            // }else{
            //     if(a[j-1]>a[j]){//左边大于当前
            // int temp=a[j];
            // a[j]=a[j-1];
            // a[j-1]=temp;
                a[j]=a[j-1];
            //     }else{//左边 小于等于当前
            //         break;
            //     }
            // }
        }
        a[j]=e;
    }
    printf("[");
    for(int i=0;i<len;i++){
        if(i==len-1){
            printf("%d]\n",a[i]);
        }else{
            printf("%d,",a[i]);
        }
    }
}

四（头尾指针法）

class Solution {
    public int[] sortArrayByParity(int[] A) {
        if(A==null||A.length==1){
            return A;
        }
        int left=0;//向右走
        int right=A.length-1;//向左走
        while(left<right){
            while(left<right&&A[left]%2==0){//偶数的话就一直走
            //找到奇数坐标就跳出循环
                ++left;
            }
            while(left<right&&A[right]%2==1){//奇数的话就一直走
            //找到偶数坐标就跳出循环
                --right;
            }
            //交换后
            swap(A,left,right);
        }
        return A;
    }
    public void swap(int[] A, int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
}

算法效率

第五种：说不上来的方法，不过你应该能看的懂

创建一个和原数组长度相同的新数组用来存我们需要的元素，先遍历原来的数组，如果是偶数就将这个数放在新数组的左边，反之放到右边。

class Solution {
    public int[] sortArrayByParity(int[] A) {
         int len = A.length;
        int[] res = new int[len];
        int leftIndex = 0;
        int rightIndex = A.length - 1;
        for (int a : A) {
            if (a % 2 == 0) {
                res[leftIndex] = a;
                leftIndex++;
            } else {
                res[rightIndex] = a;
                rightIndex--;
            }
        }
        return res;
    }
}