数组的排序算法

算法=数据结构+程序代码
1.排序:
假设含有n个记录的序列为{R1，R2，…Rn},其相应的关键字序列为{K1，K2，…,Kn}。将这些记录重新排序为{Ri1,Ri2,…Rin},使得相应的关键字值满足条Ki1<=Ki2<=…<=Kin,这样的一种操作称为排序。
通常来说，排序的目的是快速查找，例如二分查找。
2.衡量排序算法的优劣：
（1）时间复杂度：分析关键字的比较次数和记录的移动次数
（2）空间复杂度：分析排序算法中需要多少辅助内存
（3）稳定性：若两个记录A和B的关键字值相同，但排序后A、B的先后次序保持不变，则称这种排序算法是稳定的。
3.排序算法分类：
内部排序：整个排序过程不需要借助于外部存储器（如磁盘等），所有排序操作都在内存中完成
外部排序：参与排序的数据非常多，数据量非常大，计算机无法把整个排序过程放在内存中完成，必须借助外部存储器（如磁盘）。外部排序最常见的是多路归并排序。可以认为外部排序是由多次内部排序组成。
4.算法的5大特性
输入：有0个或多个输入数据，这些输入必须要有清楚的描述和定义
输出：至少有1个或者多个输出结果，不可以没有输出结果
有穷性（有限性）：算法在有限的步骤之后会自动结束，而不会死循环，并且每一个步骤可以在可接受的时间内完成
确定性（明确性）：算法中的每一步都有明确的含义，不会出现二义性
可行性（有效性）：算法的每一步都是清楚可行的，能让用户使用纸笔计算出答案。
5.十大内部排序算法
选择排序：直接选择排序、堆排序
交换排序：冒泡排序、快速排序（这两种会写出代码）
插入排序：直接插入排序、折半插入排序、Shell排序
归并排序：
桶排序：
基数排序：
5.1快速排序算法
快排思想：
1）先从数列中取出一个数作为基准数，记为key。
2）移动下标，将不小于x的数全放到它的右边，不大于x的数全放到它的左边（这样key的位置左边的没有大于key的，右边的没有小于key的，只需对左右区间排序即可）
3）再对左右区间重复第二步，直到各区间只有一个数

public class QuickSortTest {
	public static void main(String[] args) {
		int[] arr=new int[] {12,5,8,9,10};
		System.out.println("排序前的结果是:");
		for(int i=0;i<arr.length;i++) {
			System.out.print(arr[i]+"\t");
		}
		System.out.println();
		quickSort(arr,0,arr.length-1);
		System.out.println("排序后的结果是：");
		for(int i=0;i<arr.length;i++) {
			System.out.print(arr[i]+"\t");
		}
	}
	public static void quickSort(int[] arr,int left,int right) {		//快速排序
		if(arr==null || left>right) {
			return ;
		}
		if(left > right) {
			return ;
		}
		int l=left;
		int r=right;
		int key=arr[left];
		while(l != r) {
			while(arr[r]>=key && l<r) {		//左移
				r--;
			}
			while(arr[l]<=key && l<r) {		//右移
				l++;
			}
			if(l<=r) {			//交换l和r的位置
				int temp=arr[l];
				arr[l]=arr[r];
				arr[r]=temp;	
			}
		}
		arr[left]=arr[l];
		arr[l]=key;
		quickSort(arr,l+1,right);	//递归对右侧的子序列排序
		quickSort(arr,left,l-1);	//递归对左侧的子序列排序
	}
 
}

5.2 选择排序算法
选择排序思想：
1）在未排序的n个数（a[0]~a[n-1]）中找到最小值，将它与a[0]交换；
2）在剩下未排序的n-1个数（a[1]~a[n-1]）中找到最小值，将它与a[1]交换；
…
依次如下，在第n-1步，在未排序的2个数（a[n-2]~a[n-1]）中找到最小值，将它与a[n-2]交换。

public class SortTest02 {
	public static void main(String[] args) {
	
		int[] arr = new int[] {12,5,6,87,8,26};
		System.out.println("排序前的数组是：");
		for(int i=0;i<arr.length;i++) {
			System.out.print(arr[i]+"\t");
		}
		for(int i=0;i<arr.length-1;i++) {
			int index=i;
			for(int j=i+1;j<arr.length;j++)
				if(arr[j] < arr[index]) index=j;
				int temp=arr[index];
				arr[index]=arr[i];
				arr[i]=temp;	
		}
		System.out.println();
		System.out.println("排序后的数组是：");
		for(int i=0;i<arr.length;i++) {
			System.out.print(arr[i]+"\t");
		}
	}
}

5.3 冒泡排序
冒泡排序思想：
从第一个元素开始比较相邻的两个元素，如果第一个比第一个大或小，就互换它们的位置，这样先比较完一次，然后抛弃最大或最小的继续比较，直到排序完成。

package com.jd.wds;

public class SorTest01 {
	public static void main(String[] args) {
		int[] arr = new int[] {15,6,8,16,28,9,13};
		System.out.println("排序前的结果是：");
		for(int i=0;i<arr.length;i++) {
			System.out.print(arr[i]+"\t");
		}
		for(int i=0;i<arr.length-1;i++) {		//
			for(int j=0;j<arr.length-i-1;j++) {
				if(arr[j]>arr[j+1])
				{
					int temp=arr[j];
					arr[j]=arr[j+1];
					arr[j+1]=temp;
				}
			}
		}
		System.out.println();
		System.out.println("冒泡排序后的结果是：");
		for(int i=0;i<arr.length;i++) {
			System.out.print(arr[i]+"\t");
		}
	}
}

排序算法总结：