java常见的排序算法

package com.coding;

import java.util.Arrays;

public class Coding9 {
	private int[] src = new int[] { 38, 17, 16, 16, 7, 31, 39, 32, 2, 11 };

	public static void main(String[] args) {
		Coding9 c9 = new Coding9();
		// c9.SelectionSort(c9.src);//选择排序
		//c9.BubbleSort(c9.src);// 冒泡排序
		//c9.quickSort(c9.src,0,c9.src.length-1);// 快速排序
		//Arrays.sort(c9.src);// Arrays类自带的快速排序
		c9.InsertSort(c9.src);//插入排序
		for (int i : c9.src) {
			System.out.print(i + "|");
		}
	}

	/*
	 * 选择排序 选择排序的基本思想是遍历数组的过程中， 以 i 代表当前需要排序的序号， 则需要在剩余的中找出其中的最小值， 然后将找到的最小值与 i
	 * 指向的值进行交换。 因为每一趟确定元素的过程中都会有一个选择最值的子流程，所以人们形象地称之为选择排序。
	 * 
	 * 时间复杂度和空间复杂度分别为 O(n^2)和 O(1)
	 */
	public void SelectionSort(int[] src) {
		int len = src.length;
		int temp;
		for (int i = 0; i < len; i++) {
			temp = src[i];
			int j;
			int samllestLocation = i;// 最小数的下标
			for (j = i + 1; j < len; j++) {
				if (src[j] < temp) {
					temp = src[j];// 取出最小值
					samllestLocation = j;// 取出最小值所在下标
				}
			}
			src[samllestLocation] = src[i];
			src[i] = temp;
		}
	}

	/*
	 * 冒泡排序 冒泡排序可以算是最经典的排序算法了，实现方法最简单，两层 for循环， 里层循环中判断相邻两个元素是否逆序，
	 * 是的话将两个元素交换，外层循环一次，就能将数组中剩下的元素中最值的元素“浮”出，所以称之为冒泡排序。
	 * 
	 * 时间复杂度和空间复杂度分别为 O(n^2)和 O(1)
	 */
	public void BubbleSort(int[] src) {
		int len = src.length;
		for (int i = 0; i < len; i++) { // 最多做n-1趟排序
			for (int j = 0; j < len - i - 1; j++) {
				if (src[j] > src[j + 1]) { // 把大的值交换到后面
					int temp = src[j];
					src[j] = src[j + 1];
					src[j + 1] = temp;
				}

			}
		}
	}

	/*
	 * 快速排序 快速排序也是用归并方法实现的一个“分而治之”的排序算法， 它的魅力之处在于它能在每次partition（排序算法的核心所在）
	 * 都能为一个数组元素确定其排序最终正确位置（一次就定位准，下次循环就不考虑这个元素了）。
	 * 平均时间复杂度是n*logn 
	 */
	public void quickSort(int[] src, int left, int right) {
		int middle, tempDate;
		int i, j;
		i = left;
		j = right;
		middle = src[(i + j) / 2];
		do {
			// 找出左边比中间值大的数
			while (src[i] < middle && i < right)
				i++;
			// 找出右边比中间值小的数
			while (src[j] > middle && j > left)
				j--;

			if (i <= j) {
				// 将左边大的数和右边小的数进行替换
				tempDate = src[i];
				src[i] = src[j];
				src[j] = tempDate;
				i++;
				j--;
			}
		} while (i <= j);
		// 当两者交错时停止
		if (i < right) {
			quickSort(src, i, right);
		}
		if (j > left) {
			quickSort(src, left, j);
		}
	}
	/*
	 * 插入排序
	 * 插入排序就是每一步都将一个待排数据按其大小插入到已经排序的数据中的适当位置，直到全部插入完毕
	 * 时间复杂度为 O(n^2)
	 */
	public void InsertSort(int[] src)
    {
       int len=src.length;
       for(int i=1;i<len;i++)
       {
           int j;
           int temp=src[i];
           for(j=i;j>0;j--)
           {
              if(src[j-1]>temp)
              {
                  src[j]=src[j-1];
                  
              }else//如果当前的数，不小前面的数，那就说明不小于前面所有的数，
                   //因为前面已经是排好了序的，所以直接通出当前一轮的比较
                  break;
           }
           src[j]=temp;
       }
    }

	
	
	

}