java几种典型的排序,冒泡，插入，选择等

相关术语说明：

• 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；

• 不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；

• 内排序：所有排序操作都在内存中完成；

• 外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；

• 时间复杂度： 一个算法执行所耗费的时间。

• 空间复杂度：运行完一个程序所需内存的大小。

几种算法的空间复杂度以及时间复杂度

1.1 算法思路描述：

• 比较相邻的元素。如果第一个比第二个大，就交换它们两个；

• 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；

• 针对所有的元素重复以上的步骤，除了最后一个；

• 重复步骤1~3，直到排序完成。

1.2 动图演示

1.3 代码

    public static void name(int[] arr,int length) {
	for(int i=0; i< length - 1; i++){
	   for(int j = 0; j < length - 1 - i; j++){
	     if(arr[j] > arr[j+1]){
	        int temp = arr[j];
	        arr[j] = arr[j+1];
	        arr[j+1] = temp;
	     }
	   }
	}
    }

冒泡排序虽然简单，但是还是有可以优化的地方，下面为冒泡排序的优化版本

/**
     * 改进版冒泡排序，主要维护了一个尾部边界索引，如果交换到后面不需要交换，则下次遍历后面无需遍历
     * @param arr
     * @param length
     */
    public static void bubbleSort(int[] arr,int length){
    	int flag = length;
    	int lastIndex;
    	while(flag > 0){
    		lastIndex = flag;
    		flag = 0;
    		for(int i = 1;i < lastIndex;i++){
    			if(arr[i] < arr[i - 1]){
    				int temp = arr[i];
    				arr[i] = arr[i - 1];
    				arr[i - 1] = temp;
    				flag = i;
    			}
    		}
    	}
    }

2.1 算法思路描述：

• 第一趟比较前两个数，然后把第二个数按大小插入到有序表中
  

• 第二趟把第三个数据与前两个数从前向后扫描，把第三个数按大小插入到有序表中；

• 依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程

2.2 图示

2.3 代码演示

/**
     * 插入排序
     * @param arr
     * @param length
     */
    public static void insertionSort(int[] arr,int length){
    	for(int i = 1; i < length; i++){
    		for(int j = i; j > 0 && arr[j] < arr[j - 1];j--){
				int temp = arr[j];
				arr[j] = arr[j - 1];
				arr[j - 1] = temp;
    		}
    	}
    	
    }

同样，插入排序也是可以优化的。

/**
     * 插入排序
     * @param arr
     * @param length
     */
    public static void insertionSort(int[] arr,int length){
    	
    	//改进版，不需要每次都交换，而是将该值拿出来，与前面对比，如果比前面小，则将前面一个赋值给后面一个，直到前面没有更小的，此时将该值赋值给当前
    	for(int i = 1; i < length; i++){
    		int e = arr[i];
    		int j;
    		for(j = i; j > 0 && arr[j - 1] > e;j--){
			arr[j] = arr[j - 1];
    		}
    		arr[j] = e;
    	}
    }

3.1 算法思路描述：

• 第一趟：从n个记录中找出关键码最小的记录和第一个记录交换；
  

• 第二趟：从第二个记录开始的n-1个记录中再选出关键码最小的记录与第二个记录交换，以此类推......

• 第i趟，则从第i个记录开始的n-i+1个记录中选出关键码最小的记录与第i个记录交换，直到整个序列按关键码有序。

3.2 图示

3.3 代码演示

/**
     * 选择排序
     */
    public static void selectSort(int[] arr,int length){
    	for(int i = 0;i < length; i++){
    		int minIndex = i;
    		for(int j = i + 1; j < length;j++){
    			if(arr[j] < arr[minIndex]){
    				minIndex = j;
    			}
    		}
    		int temp = arr[i];
    		arr[i] = arr[minIndex];
    		arr[minIndex] = temp;
    	}
    }

总结：几种算法的思想大体类似，关键在于交界点的思考，不然容易出错，下次研究快速排序以及归并排序。