基本排序算法

import java.util.Arrays;

public class AllSort {
	public static int[] bubbleSort(int[] arr) {
		int len = arr.length;
		for (int i = 0; i < len-1; i++) {
			for (int j = 0; j < len-1-i; j++) {
				if (arr[j] > arr[j+1]) {
					int temp = arr[j+1];
					arr[j+1] = arr[j];
					arr[j] = temp;
				}
			}
		}
		return arr;
	}
	
	public static int[] selectSort(int[] arr) {
		int len = arr.length;
		int minIndex, temp;
		for (int i = 0; i < len-1; i++) {
			minIndex = i;
			for (int j = i+1; j < len; j++) {
				if (arr[j] < arr[minIndex]) {
					minIndex = j;
				}
			}
			temp = arr[i];
	        arr[i] = arr[minIndex];
	        arr[minIndex] = temp;
		}
		return arr;
	}
	
	public static int[] insertSort(int[] arr) {
		int len = arr.length;
	    int preIndex, current;
	    for (int i = 1; i < len; i++) {
	        preIndex = i - 1;
	        current = arr[i];
	        while (preIndex >= 0 && arr[preIndex] > current) {
	            arr[preIndex + 1] = arr[preIndex];
	            preIndex--;
	        }
	        arr[preIndex + 1] = current;
	    }
	    return arr;
	}
	
	public static int[] shellSort(int[] arr) {
		 int len = arr.length;
		    for (int gap = (int) Math.floor(len / 2); gap > 0; gap = (int) Math.floor(gap / 2)) {
		        
		        for (int i = gap; i < len; i++) {
		            int j = i;
		            int current = arr[i];
		            while (j - gap >= 0 && current < arr[j - gap]) {
		                 arr[j] = arr[j - gap];
		                 j = j - gap;
		            }
		            arr[j] = current;
		        }
		    }
		    return arr;
	}
	/////////////////////////////////////
	public static int[] mergeSort(int[] a,int low,int high){
        int mid = (low+high)/2;
        if(low<high){
        	mergeSort(a,low,mid);
        	mergeSort(a,mid+1,high);
            //左右归并
            merge(a,low,mid,high);
        }
        return a;
    }
     
    public static void merge(int[] a, int low, int mid, int high) {
        int[] temp = new int[high-low+1];
        int i= low;
        int j = mid+1;
        int k=0;
        // 把较小的数先移到新数组中
        while(i<=mid && j<=high){
            if(a[i]<a[j]){
                temp[k++] = a[i++];
            }else{
                temp[k++] = a[j++];
            }
        }
        // 把左边剩余的数移入数组 
        while(i<=mid){
            temp[k++] = a[i++];
        }
        // 把右边边剩余的数移入数组
        while(j<=high){
            temp[k++] = a[j++];
        }
        // 把新数组中的数覆盖nums数组
        for(int x=0;x<temp.length;x++){
            a[x+low] = temp[x];
        }
    }
	////////////////////////////////////
    public static void quickSort(int[] arr,int low,int high) {
		if (low < high) {
		int a = Partition(arr, low, high);
		quickSort(arr, low, a-1);
		quickSort(arr, a+1, high);
		}
      }
	
	public static  int Partition(int[] arr, int low, int high) {
		int tmp = arr[low];
		while (low < high) {
			while (low < high && arr[high] > tmp) {
				high--;
			}
			arr[low] = arr[high];
			while(low < high && arr[low] < tmp) {
				low++;
			}
			arr[high] = arr[low];
		}
		arr[low] = tmp;
		return low;
	}

public static void main(String[] args) {
	int[] arr = {3,5,15,26,2,25,27,9,34,36,7,29,4};
	
	int[] bubble = bubbleSort(arr); //冒泡排序
	
	int[] select = selectSort(arr); //选择排序
	
	int[] insert = insertSort(arr); //插入排序
	
	int[] shell = insertSort(arr); //希尔排序
	
	int[] merge = insertSort(arr); //归并排序
	
	 //quickSort(arr, 0, arr.length-1); //快速排序

     System.out.println(Arrays.toString(bubble));
     
     System.out.println(Arrays.toString(select));
     
     System.out.println(Arrays.toString(insert));
     
     System.out.println(Arrays.toString(shell));
     
     System.out.println(Arrays.toString(merge));
}
}

Java不用递归的迭代快速排序示例

import java.util.Arrays;
import java.util.Scanner;
import java.util.Stack;

/**
 * Java Program to implement Iterative QuickSort Algorithm, without recursion.
 *
 * @author WINDOWS 8
 */
public class Sorting {

    public static void main(String args) {

        int unsorted = {34, 32, 43, 12, 11, 32, 22, 21, 32};
        System.out.println("Unsorted array : " + Arrays.toString(unsorted));

        iterativeQsort(unsorted);
        System.out.println("Sorted array : " + Arrays.toString(unsorted));
    }


    /*
     * iterative implementation of quicksort sorting algorithm.
     */
    public static void iterativeQsort(int numbers) {
        Stack stack = new Stack();
        stack.push(0);
        stack.push(numbers.length);

        while (!stack.isEmpty()) {
            int end = stack.pop();
            int start = stack.pop();
            if (end - start < 2) {
                continue;
            }
            int p = start + ((end - start) / 2);
            p = partition(numbers, p, start, end);

            stack.push(p + 1);
            stack.push(end);

            stack.push(start);
            stack.push(p);

        }
    }

    /*
     * Utility method to partition the array into smaller array, and
     * comparing numbers to rearrange them as per quicksort algorithm.
     */
    private static int partition(int input, int position, int start, int end) {
        int l = start;
        int h = end - 2;
        int piv = input[position];
        swap(input, position, end - 1);

        while (l < h) {
            if (input[l] < piv) {
                l++;
            } else if (input[h] >= piv) {
                h--;
            } else {
                swap(input, l, h);
            }
        }
        int idx = h;
        if (input[h] < piv) {
            idx++;
        }
        swap(input, end - 1, idx);
        return idx;
    }

    /**
     * Utility method to swap two numbers in given array
     *
     * @param arr - array on which swap will happen
     * @param i
     * @param j
     */
    private static void swap(int arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}

https://www.jdon.com/51841

参考

https://www.cnblogs.com/onepixel/articles/7674659.html