前言
上周星期天，我跟一個前一段時間在深圳找作業的學長聊天，他告訴 我他找了一份5位數薪資的作業，當時我也很高興，然后我接著問了他遇到了哪些面試題，然后他就跟我分享了一道題，題目是這樣的：
給定一個整型陣列，其中的數值有正有負（我們暫時認為0也算是正數部分），現在請調整位置，把所有負值調到陣列的左邊，把所有正直調到陣列右邊，
思路
用一個指標i從前往后找第一個正數，用一個指標j從后往前找第一個負數，找到以后并且i<j,那么就將他們位置互換，這樣，就完成了排序，代碼如下：
package interview;
/**
* @author xing xing
*/
public class ArraySort {
public static void main(String[] args) {
//定義一個陣列
int [] array = {1,-2,-4,5,9,-3,-8,6};
arraySort(array);
print(array);
}
public static void arraySort(int[] array) {
int j = array.length-1;
int i = 0;
//定義變數盡量在外面定義，避免重復創建變數浪費空間
int temp;
while (i < j) {
//從前面開始找，找到第一個正數
while (array[i] < 0) {
i++;
}
//從后面開始找，找到第一個負數
while (array[j] >= 0) {
j--;
}
//如果這時候i < j ,就將他們交換位置
if (i < j) {
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
//交換完位置以后，兩個指標往后移動尋找下一個
i++;
j--;
}
}
//列印陣列
public static void print(int[] array) {
for (int i = 0; i < array.length; i++) {
System.out.println(array[i]);
}
}
}
時間復雜度和空間復雜度都很可觀，前者為O(n),后者為O(1)，這樣就大功告成了，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/224792.html
標籤：java
上一篇：Java基礎學習1