算法学习之路(排序)

1.选择排序

时间复杂度为O(N^2),额外空间复杂度为O(1)

代码实现(java):

 1 public static void SelectionSort(int[] arr){
 2     if(arr == null || arr.length < 2){
 3         return;
 4     }
 5     for(int i = 0;i < arr.length-1;i++){
 6         int minIndex=i;
 7         for(int j=i+1;j < arr.length;j++){
 8             minIndex = arr[j]>arr[minIndex]?j:minIndex;
 9         }
10         swap(arr,i,minIndex);
11     }
12 }
13 public static void swap(int[] arr,int i,int j){
14     int tmp = arr[i];
15     arr[i] = arr[j];
16     arr[j] =tmp;
17 }

注解:

在代码的最开始我们就要把特殊情况考虑清楚,选择排序只有一种特殊情况就是当数组的元素个数为0或者1时,整个数组本身就是一个有序的数组,我们是不需要对数组进行排序操作的;

选择排序是我们假定第一个位置的值就是最小值,然后我们从数组的第一个位置的值依次的与后面的元素进行比较,每次比较之后将两者中较小的值的位置赋给一个变量minindex,当我们从第一个位置一直比较到最后一个位置之后我们就已经选择出了整个数组中最小的那个值的位置,我们再将这个最小值的位置与第一个位置进行交换,之后我们在从第二个位置开始执行上述操作,直至整个数组排序完成,我们这样操作就会得到一个升序的数组。

2.冒泡排序

时间复杂度为O(N^2)

代码实现(Java)

 1 public static void Bubblesort(int[] arr){
 2     if(arr == null || arr.length<2){
 3         return;
 4     }
 5     for(int e = arr.length-1;e > 0;e--){
 6         for(int i = 0;i < e;i++){
 7             if(arr[i] > arr[i+1])
 8                 swap(arr,i,i+1);
 9         }
10     }
11 }
12 public static void swap(int[] arr,int i,int j){
13     arr[i]=arr[i]^arr[j];
14     arr[j]=arr[i]^arr[j];
15     arr[i]=arr[i]^arr[j];
16 }

注解:

同样也是一个数组我们把每个元素的位置进行编号0,1,2,3,4,5,6,7······,冒泡排序就是第0个位置与第1个位置比较谁大谁往右移动,当从第0个位置到最后一个位置全部移动完毕,最后一个位置的元素就确定下来了,它就是整个数组中最大的那个数,因为一共有arr.length个元素,所以要进行arr.length-1次循环,所以第一个for循环规定交换操作的起始位置和结束位置,第二个for循环是用来依次交换相邻两个数的位置将大的置于右端。

上一篇:HDOJ(HDU) 2088 Box of Bricks(平均值)


下一篇:排序算法1 - 选择排序