数据结构之常用排序算法理解
1.选择排序:
遍历数组,每一次遍历找出一个最小值放在数组前面,步骤如下:
2.插入排序:
这个算法可以描述为:
for(int i=1; i<a.length; i++) {将a[i]插入到已排号序的子数列中,然后a[0]->a[i]就是有序的}?
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