Java練習題(四)：一種特殊排序法

最近希望花點時間，重新訓練自己解題的能力，故找了一些經典的題目進行練習。
解法不一定是最有效率、最低複雜度、最佳效能的，完全是依照自己的想法做！

---

假設題目要求：給一串整數數列，並根據數列長度為奇數或偶數有不同排序方式，
ex: 若數列長度為奇數{1, 2, 3, 4, 5}，排序後應為： {2, 4, 5, 3, 1}
ex: 若數列長度為偶數{1, 2, 3, 4, 5, 6}，排序後應為： {2, 4, 6, 5, 3, 1}

觀察題目後瞭解，關鍵為最大數的位置及排序方法，若數列長度為奇數，則最大數位置為數列長度 / 2 ，之後根據大小順序為最大數左邊、右邊、左邊、右邊...依序置入。若數列長度為偶數，則最大數位置為數列長度 / 2 - 1，之後根據大小順序為最大數右邊、左邊、右邊、左邊...依序置入。

解題構想：由使用者輸入一數字N, 之後生成數列長度為N的隨機正整數, 並用 Bubble Sort 針對原始數列進行排列。之後根據數列長度為奇數或偶數進行排序，排序時先將最大數插入其位置，之後以最大數將數列分割為左右兩邊，分別以兩個 int 變數儲存下一個數在左邊與右邊的位置；再以一 int 變數判斷目前位置該為最大數的左邊或右邊。

程式碼：

	package algorithms;
	import java.util.Scanner;
	public class SpecialSorting {
	static int numSize = 0;
	static int[] aryRandomNumbers;
	static int[] afterSorting;
	public static void main(String[] args) {
	// TODO Auto-generated method stub
	Scanner scanner = new Scanner(System.in);
	System.out.println("input a number, it will generating n-size random rumber");
	numSize = scanner.nextInt();
	afterSorting = new int[numSize];
	//產生數列長度為N的隨機正整數數列
	getRandomNumbers(numSize);
	//使用泡沫排序法排序
	bubbleSort();
	sequentialSorting();
	}
	static int putCount = -1; //-1:middle, 0:left, 1:right
	static int putLeft = 0; //放在左邊的位置
	static int putRight = 0; //放在右邊的位置
	int putMiddle = 0;
	private static void sequentialSorting() {
	// TODO Auto-generated method stub
	for(int i = aryRandomNumbers.length-1; i >= 0; i--) {
	if(numSize%2 == 0) {
	insertNumber(putCount, "even", aryRandomNumbers[i]);
	} else {
	insertNumber(putCount, "odd", aryRandomNumbers[i]);
	}
	}
	}
	private static void insertNumber(int flag, String size, int number) {
	// TODO Auto-generated method stub
	switch(flag) { //-1:middle, 0:left, 1:right
	case -1:
	{
	if(size.equals("even")) {
	afterSorting[numSize/2 - 1] = number;
	putLeft = numSize/2 - 1;
	putRight = numSize/2 - 1;
	putCount = 1;
	}
	else {
	afterSorting[numSize/2] = number;
	putCount = 0;
	putLeft = numSize/2;
	putRight = numSize/2;
	}
	break;
	}
	case 0:
	{
	putCount = 1;
	putLeft = putLeft-1;
	afterSorting[putLeft] = number;
	break;
	}
	case 1:
	{
	putCount = 0;
	putRight = putRight+1;
	afterSorting[putRight] = number;
	break;
	}
	}
	System.out.println("\nsequential Sorting");
	for(int element:afterSorting ) {
	System.out.print(element + " ");
	}
	}
	}

view raw sort hosted with ❤ by GitHub