数据结构之常用排序算法理解

1.选择排序:

遍历数组,每一次遍历找出一个最小值放在数组前面,步骤如下:

1. 将currMin设为a[0],遍历a[1]->a[n-1],只要a[i]小于a[0],进行a[0]与a[i]的交换
2. 将currMin设为a[1],遍历a[2]->a[n-1]
3. 最后一个currMin为a[n-2],比较a[n-2]与a[n-1]

代码如下:

 

for(int i=0; i<arr.length -1; i++) {
    int currMin = arr[i];
    int currMinIndex = i;
    for (int j=i+1; j<arr.length; j++) {
        if(currMin > arr[j]) {
            currMin = arr[j];
            currMinIndex = j;
        }
    }
    if(currMinIndex != i) {
        list[currMinIndex] = a[i];
        a[i] = currMin;
    }
}

 

2.插入排序:

这个算法可以描述为: 将a[i]插入到已排号序的子数列中,然后a[0]->a[i]就是有序的

for(int i=1; i<arr.length; i++) {
    int currEle = arr[i];
    for (int j =i-1; j>=0&&arr[j]>currEle; j--){
        arr[j+1] = arr[j]
    }
    arr[j+1] = currEle

}

 

3.冒泡排序

遍历数组,每一次遍历后将值最大的元素交换到数组尾部,关键代码如下:

for(int out=1; out<a.lenght; out++){
    for (int in=0; in<a.length-out; in++)
        if(a[i] > a[i+1]){
            int temp = a[i];
            a[i] = a[i+1]
            a[i+1] = temp;
        }
        
}

 

4.归并排序

归并排序通过递归实现,思想非常容易理解:

public static void mergeSort(int[] list){
		if (list.length <1) {
			mergeSort(list[0->list.length/2]);
			mergeSort(list[list.length/2+1 ->list.length]);
			merge(int[firstHalfList], int[secondHalfList]);			
		}
	}
	
	public static int[] merge(int[] first, int[] second){
		int index1=0,index2=0,index3=0;
		int[] result;
		//将两个数组中的数据按大小先后存储到result中
		while(index1<first.length && index2<second.length){
			if(first[index1]<second(index2)){
				result[index3] =first[index1];
				++index1;
				++index3
			} else {
				result[index3] =second[index2];
				++index2;
				++index3
			}
			
		}
		//将剩下最大的数据,单独再追加到result表
		while (index1 <first.length) {
			result[index3++] = first[index1++];
		}
		while (index2 < second.length) {
			result[index3++] = first[index2++];
		}
	}

 

5.快速排序

快速排序跟归并排序一样采用的递归的方法实现:

public static void quickSort(int[] list){
		quickSort(list, 0, list.length-1);
		
	}
	
	public static void quickSort(int list[], int first, int last){
		if (last>first){
			int pindex = partition(list, first, last);
			quickSort(list, first, pindex-1);
			quickSort(list, pindex, last);
			
		}
	} 

• 快速排序关键是pindex的计算,在计算pindex的时候, list[0, pindex-1]的元素都比a[pindex]小,list[pindex+1, length-1]中的元素都比a[pindex]大
• 在进行partition的时候,数组中元素进行交换

 

评论

1 楼 留下的祝福 2013-10-29  

快速排序和冒泡排序属于选择排序这一大类！