我为什么复习算法?
算法是编程的灵魂,以前在学校的时候上数据结构,算法都是会的就写,不会就抄。刚出来找工作面试问的还是基础和算法,算法可以体现你的基础扎不扎实,一个聪明的脑子应该是看一遍算法描述就很快的写出来,我第一次面试的时候让我写快排(快速排序),哇,好熟悉,一写各种出错,趁毕业之前再来过一遍基础算法吧。
快速排序
快速排序(Quicksort)是对冒泡排序的一种改进。由C.
A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
演示:先从后往前,找比key小的值,找到之后与i互换,再从前往后找比key大的值,找到之后与j互换,一直重复直到i=j时一轮结束,结束之后的数组小的都在前面,大的都在后面,在小的和大的部分分别执行以上步骤,直到结束
key i j i/j满足条件 互换
1 6 0 9 array[9]<=key a[9]<-->a[0] [4,2,7,4,3,9,8,89,20,6]
2 6 2
9 array[2]>=key a[2]<-->a[9] [4,2,6,4,3,9,8,89,20,7]
3
6 2 4 array[4]<=key a[4]<-->a[2] [4,2,3,4,6,9,8,89,20,7]
此时以6将数组分成两拨 前面全比6小 后面全部比6大
前面的继续进行如上述排序
比6小的部分
[4,2,3,4]->[3,2,4,4]->[2,3,4,4]
比6大的部分
[9,8,89,20,7]->[7,8,89,20,9]
[8,89,20,9]
[89,20,9]->[9,20,89]
[20,89]
代码示例:
Java:
// 快速排序 public static void quick_sort(int array[], int start, int end) { int i = start; int j = end; int key = array[start]; while (i < j) { while (array[j] >= key) { System.out.print("_j_"); j--; } if (i < j) { int temp = array[j]; array[j] = array[i]; array[i] = temp; System.out.print("j------------------"); i++; } while (array[i] <= key) { System.out.print("_i_"); i++; } if (i < j) { int temp = array[j]; array[j] = array[i]; array[i] = temp; System.out.print("i------------------"); j--; } } System.out.print("i=" + (i + 1) + ",j=" + (j + 1) + ",key=" + key + " "); for (int a : array) { System.out.print(a + ","); } System.out.print("\n"); if (i > start) quick_sort(array, start, j - 1); if (j < end) quick_sort(array, i + 1, end); }
Python:
print "quick_sort_example"; List=[6,2,7,4,3,9,8,89,20,4] def quick_sort(a,start,end): i=start j=end key=a[start] while i<j: while i<j and a[j]>=key: print 'J' j=j-1 if i<j: t=a[j] a[j]=a[i] a[i]=t #print '--------------',a i=i+1 while i<j and a[i]<=key: i=i+1 if i<j: t=a[j] a[j]=a[i] a[i]=t j=j-1 if i>start: quick_sort(a,start,j-1) if j<end: quick_sort(a,i+1,end) print "List before sort:",List quick_sort(List,0,len(List)-1) print "List after sort:",List