八大排序算法总结（2）

归并排序；

 1 //merge sort
 2     public static void merge(int[] a,int aux[],int lo ,int mid,int hi ){
 3         int i = lo;
 4         int j = mid+1;
 5         //copy a
 6         for (int k = lo; k <= hi; k++) 
 7             aux[k] = a[k];
 8         //merge
 9         for(int k = lo;k<=hi;k++){        
10             //先判断是否越界
11             if(i>mid)                    a[k]=aux[j++];
12             else if(j>hi)                a[k]=aux[i++];
13             // merge
14                 else if(aux[j]<=aux[i])     a[k]=aux[j++];
15                 else                     a[k]=aux[i++];
16         }
17     }
18     public static void mergesort(int[] a,int aux[],int lo,int hi) {
19         //边界条件
20                 if(lo>=hi) return ;
21         int mid = (hi-lo)/2+lo;
22         mergesort(a,aux, lo, mid);
23         mergesort(a,aux, mid+1, hi);
24         merge(a,aux, lo, mid, hi);
25         
26     }
27     public static void mergeSort(int[] a){
28         int aux[] = new int[a.length];
29         mergesort(a,aux, 0, a.length-1);
30     }

 1 ef merge(a,aux,lo,mid,hi):
 2     if(lo>=hi) :
 3         return a
 4 
 5     ####merge之前copy
 6     aux = a.copy()
 7     
 8     i = lo
 9     j = mid + 1
10     k = lo
11     while i<=mid and j<=hi:
12         if(aux[i]<aux[j]):
13             a[k] = aux[i];i+=1;k+=1
14         else:
15             a[k] = aux[j];j+=1;k+=1
16     while i<=mid:
17         a[k] = aux[i] ;i+=1;k+=1
18     while j<=hi:
19         a[k] = aux[j] ;j+=1;k+=1
20     return a
21 def merge_sort(a,aux,lo,hi):
22     if(lo>=hi):
23         return
24     mid = int((hi-lo)/2) +lo
25     print(a,aux,lo,mid,hi)
26     merge_sort(a,aux,lo,mid)
27     merge_sort(a,aux,mid+1,hi)
28     merge(a,aux,lo,mid,hi)
29     return a
30 def merge_sort1(a):
31     merge_sort(a,a.copy(),0,len(a)-1)

快速排序：

 1 //quick sort
 2     //partion
 3     private static int partion(int[] a ,int lo,int hi) {
 4         int v = a[lo];
 5         int i = lo ,j=hi+1;
 6         while(true){
 7             while(a[++i]<v) if(i>=hi) break;
 8             while(a[--j]>v) if(j<=lo) break;
 9             if(i>=j) break;
10             swap(a, i, j);
11         }
12         swap(a, lo, j);
13         return j;
14     }
15     public static void partionsort(int[] a,int lo,int hi) {
16         if(lo>=hi) return;
17         int j = partion(a, lo, hi);
18         partionsort(a, lo, j);
19         partionsort(a, j+1, hi);
20         
21     }
22     public static void partionSort(int[] a) {
23         partionsort(a, 0, a.length-1);
24     }
25

 1 def quick_sort1(x):
 2     def partion(a, lo, hi):
 3         '''
 4         得到数组a的划分
 5         以a[lo] 为key,最后把a[lo]放在最终排序的位置
 6         且 a[lo] 前面的比其都小，a[lo]后面的比其都大
 7         '''
 8         key = a[lo]
 9         i = lo
10         j = hi
11         while(i < j):
12             # 必须带等号
13             while(i < hi and a[i] <= key):  # 从左往右找到大于key的下标
14                 i += 1
15             while(j > lo and a[j] >= key):  # 从右往左找到小于key的下标
16                 j -= 1
17             if i < j:  # 如果下标i小于下标j则交换，没有越界
18                 swap(a, i, j)
19         swap(a, lo, j)
20         return j
21 
22     def quick_sort(x, lo, hi):
23         if lo >= hi:
24             return
25         i = partion(x, lo, hi)
26         print(x)
27         quick_sort(x, lo, i)
28         quick_sort(x, i + 1, hi)
29         print(x)
30 
31     quick_sort(x, 0, len(x) - 1)
32     return x