Javaソートアルゴリズムセット

主流のソートアルゴリズム、バブル、選択、高速ソートなどを網羅しています

package test;

import java.util.Random;

/**
 * 
 *      
 * 
 * 
 *          ：
 * 
 * 1.    （      、      、    ）；
 * 
 * 2.    （     、    ）；
 * 
 * 3.    （      、   ）；
 * 
 * 4.    ；
 * 
 * 5.    。
 * 
 * 
 * 
 *          ：
 * 
 * (1) n  ( n≤50)，              。
 * 
 * 　        ，        ；                    ，          。
 * 
 * (2)           (   )，        、            ；
 * 
 * (3) n  ，          O(nlgn)     ：    、        。
 * 
 * 
 */

public class SortAlgorithm {

	/**
	 *           
	 * @return          
	 */
	public int[] createArray() {
		Random random = new Random();
		int[] array = new int[10];

		for (int i = 0; i < 10; i++) {
			array[i] = random.nextInt(100) - random.nextInt(100);//          ，          
		}

		System.out.println("==========    ==========");
		printArray(array);

		return array;

	}

	/**
	 *             
	 * @param source
	 */
	private void printArray(int[] data) {
		for (int i : data) {
			System.out.print(i + " ");
		}
		
		System.out.println();
	}

	/**
	 *               
	 * @param data
	 * @param x
	 * @param y
	 */
	private void swap(int[] data, int x, int y) {

		int temp = data[x];
		data[x] = data[y];
		data[y] = temp;
	}

	/**
	 *     ----       
	 *   :         ，         ，                 （       ），                 。
	 *   :	    O(n^2),n^2/2；
	 *          O(n^2),n^2/4
	 * 
	 * @param data       
	 * @param sortType     
	 * @return
	 */
	public void bubbleSort(int[] data, String sortType) {
		if (sortType.equals("asc")) { //    ，     
			//      
			for (int i = 1; i < data.length; i++) {
				//           ，        
				for (int j = 0; j < data.length - i; j++) {
					if (data[j] > data[j + 1]) {
						//        
						swap(data, j, j + 1);
					}
				}
			}
		} else if (sortType.equals("desc")) { //    ，     
			//      
			for (int i = 1; i < data.length; i++) {
				//           ，        
				for (int j = 0; j < data.length - i; j++) {
					if (data[j] < data[j + 1]) {
						//        
						swap(data, j, j + 1);
					}
				}
			}
		} else {
			System.out.println("          ！");
		}

		printArray(data);//            

	}

	/**
	 * 
	 *        ----       
	 * 
	 *   :                 （   ）     ，               ，              。
	 * 
	 *   :    O(n^2),n^2/2
	 *          O(n),n
	 * 
	 *             ，      CPU        CUP   ，            。
	 * 
	 *   N    ，     CPU       ，                ，          。
	 * 
	 * @param data       
	 * @param sortType     
	 * @return
	 */
	public void selectSort(int[] data, String sortType) {
		if (sortType.equals("asc")) { //    ，     
			int index;
			for (int i = 1; i < data.length; i++) {
				index = 0;
				for (int j = 1; j <= data.length - i; j++) {
					if (data[j] > data[index]) {
						index = j;
					}
				}
				//      data.length-i index(   )   
				swap(data, data.length - i, index);
			}
		} else if (sortType.equals("desc")) { //    ，     
			int index;
			for (int i = 1; i < data.length; i++) {
				index = 0;
				for (int j = 1; j <= data.length - i; j++) {
					if (data[j] < data[index]) {
						index = j;
					}
				}
				//      data.length-i index(   )   
				swap(data, data.length - i, index);
			}
		} else {
			System.out.println("          ！");
		}

		printArray(data);//              
	}

	/**
	 * 
	 *     
	 * 
	 *   :                （      ） ,            1    。
	 * 
	 *   :    O(n^2),n^2/4
	 *          O(n),n^2/4
	 * 
	 *            ，      CPU      ，               ，         。
	 * 
	 * @param data       
	 * 
	 * @param sortType     
	 */
	public void insertSort(int[] data, String sortType) {
		if (sortType.equals("asc")) { //    ，     
			//      
			for (int i = 1; i < data.length; i++) {
				//    i+1     
				for (int j = 0; j < i; j++) {
					if (data[j] > data[i]) {
						//      j i   
						swap(data, i, j);
					}
				}
			}
		} else if (sortType.equals("desc")) { //    ，     
			//      
			for (int i = 1; i < data.length; i++) {
				//    i+1     
				for (int j = 0; j < i; j++) {
					if (data[j] < data[i]) {
						//      j i   
						swap(data, i, j);
					}
				}
			}
		} else {
			System.out.println("          ！");
		}

		printArray(data);//            
	}

	/**
	 *        
	 * 
	 * @param data    
	 */
	public void reverse(int[] data) {
		int length = data.length;
		int temp = 0;//     

		for (int i = 0; i < length / 2; i++) {
			temp = data[i];
			data[i] = data[length - 1 - i];
			data[length - 1 - i] = temp;
		}

		printArray(data);//          
	}

	/**
	 *     
	 * 
	 *          （Divide and conquer）        （list）       （sub-lists）。
	 * 
	 *    ：
	 * 
	 * 1.           ，   "  "（pivot），
	 * 
	 * 2.       ，                 ，                 （          ）。       ，
	 *           。      （partition）  。
	 * 
	 * 3.    （recursive）                          。
	 * 
	 *         ，          ，             。        ，          ，        （iteration）
	 *  ，                  。
	 * 
	 * @param data       
	 * @param low
	 * @param high
	 * 
	 * @see SortTest#qsort(int[], int, int)
	 * 
	 * @see SortTest#qsort_desc(int[], int, int)
	 */
	public void quickSort(int[] data, String sortType) {
		if (sortType.equals("asc")) { //    ，     
			qsort_asc(data, 0, data.length - 1);
		} else if (sortType.equals("desc")) { //    ，     
			qsort_desc(data, 0, data.length - 1);
		} else {
			System.out.println("          ！");
		}
	}

	/**
	 *          ，   
	 * 
	 * @param data
	 * @param low
	 * @param high
	 */
	private void qsort_asc(int data[], int low, int high) {
		int i, j, x;
		if (low < high) { //           
			i = low;
			j = high;
			x = data[i];

			while (i < j) {
				while (i < j && data[j] > x) {
					j--; //           x  
				}
				if (i < j) {
					data[i] = data[j];
					i++;
				}
				while (i < j && data[i] < x) {
					i++; //           x  
				}
				if (i < j) {
					data[j] = data[i];
					j--;
				}
			}

			data[i] = x;
			qsort_asc(data, low, i - 1);
			qsort_asc(data, i + 1, high);
		}
	}

	/**
	 * 
	 *          ，   
	 * 
	 * @param data
	 * @param low
	 * @param high
	 */
	private void qsort_desc(int data[], int low, int high) {
		int i, j, x;
		if (low < high) { //           
			i = low;
			j = high;
			x = data[i];

			while (i < j) {
				while (i < j && data[j] < x) {
					j--; //           x  
				}
				if (i < j) {
					data[i] = data[j];
					i++;
				}
				while (i < j && data[i] > x) {
					i++; //           x  
				}
				if (i < j) {
					data[j] = data[i];
					j--;
				}
			}

			data[i] = x;
			qsort_desc(data, low, i - 1);
			qsort_desc(data, i + 1, high);
		}
	}

	/**
	 * 
	 *                  (  )
	 * 
	 *             
	 * 
	 * @paramdataset
	 * @paramdata
	 * @parambeginIndex
	 * @paramendIndex
	 * @returnindex
	 */
	public int binarySearch(int[] dataset, int data, int beginIndex, int endIndex) {

		int midIndex = (beginIndex + endIndex) >>> 1; //    mid = (low + high) / 2，       

		if (data < dataset[beginIndex] || data > dataset[endIndex] || beginIndex > endIndex) {
			return -1;
		}

		if (data < dataset[midIndex]) {
			return binarySearch(dataset, data, beginIndex, midIndex - 1);
		} else if (data > dataset[midIndex]) {
			return binarySearch(dataset, data, midIndex + 1, endIndex);
		} else {
			return midIndex;
		}

	}

	/**
	 * 
	 *                  (   )
	 * 
	 *             
	 * 
	 * @paramdataset
	 * @paramdata
	 * @returnindex
	 */
	public int binarySearch(int[] dataset, int data) {
		int beginIndex = 0;
		int endIndex = dataset.length - 1;
		int midIndex = -1;

		if (data < dataset[beginIndex] || data > dataset[endIndex] || beginIndex > endIndex) {
			return -1;
		}

		while (beginIndex <= endIndex) {
			midIndex = (beginIndex + endIndex) >>> 1; //    midIndex =(beginIndex + endIndex) / 2，       

			if (data < dataset[midIndex]) {
				endIndex = midIndex - 1;
			} else if (data > dataset[midIndex]) {
				beginIndex = midIndex + 1;
			} else {
				return midIndex;
			}
		}

		return -1;
	}

	public static void main(String[] args) {

		SortAlgorithm sortTest = new SortAlgorithm();

		int[] array = sortTest.createArray();
		System.out.println("==========     (  )==========");

		sortTest.bubbleSort(array, "asc");
		System.out.println("==========     (  )==========");

		sortTest.bubbleSort(array, "desc");
		array = sortTest.createArray();
		System.out.println("==========     ==========");

		sortTest.reverse(array);
		array = sortTest.createArray();
		System.out.println("==========     (  )==========");

		sortTest.selectSort(array, "asc");
		System.out.println("==========     (  )==========");

		sortTest.selectSort(array, "desc");
		array = sortTest.createArray();
		System.out.println("==========     (  )==========");

		sortTest.insertSort(array, "asc");
		System.out.println("==========     (  )==========");

		sortTest.insertSort(array, "desc");
		array = sortTest.createArray();
		System.out.println("==========     (  )==========");

		sortTest.quickSort(array, "asc");
		sortTest.printArray(array);
		System.out.println("==========     (  )==========");

		sortTest.quickSort(array, "desc");
		sortTest.printArray(array);
		System.out.println("==========      ==========");

		System.out.println("       " + sortTest.binarySearch(array, 74) + "   。（   0  ）");
	}
}