Sorting(需要记忆较多)

[TOC]

直接选择排序和折半插入排序比较次数与序列初始无关

insert Sorting

思想：Ｖ~０~，Ｖ~１~，…，Ｖ~i－１~个对象已排好序，现要插入Ｖ~i~到适当位置

直接插入排序

每次排序时保证前面的都有序,所以每次都只需要插入一个就好

public static void insertionSort(Comparable[] a){
	int j;
    Comparable tmp;
    for(int p = 0; p < a.length(); p++){
        Comparable tmp = a[p];
        for(j = p; j > 0 && tmp.CompareTo(a[j - 1]); j--){
            a[j] = a[j - 1];
        }
        a[j] = tmp;//找到要插入的地方哩
    }//每次循环保证前面的序列有序
}

一般情况：KCN = O(n^2^) RMN = O(n^2^)

稳定性:稳定的

Binary Insert Sort

改用二分法插入的”插入排序”

Public static void BinaryInsertSort(Comparable[] a){
    for(int p = 1; p < a.length(); p++){
        int left = 0;
        int right = p - 1;
        while(left <= right){
            int middle = (left + right) / 2;
            if(a[midddle].CompareTo(a[p]) > 0){
                right = middle - 1;
            }
            else{
                left = middle + 1;
            }
        }
        Comparable tmp = a[p];
        for(int k = p - 1; k >= left; k--){
            a[k + 1] = a[k];
        }
        a[left] = tmp;//left就是我要找的位置
    }
}

比较次数：O(n * log~2~n) 与初始序列无关

稳定性:稳定

Shell Sort

public static void shellsort(Comparable[] a){
    for ( int gap = a.length / 2; gap > 0; gap /= 2 )
        for ( int i = gap; i < a.length; i++ ){ 
            Comparable tmp = a[ i ];
            int j = i;
            for ( ; j >= gap && tmp.compareTo( a[ j- gap ] ) < 0; j -= gap )
                a[ j ] = a[ j – gap ];
            a[ j ] = tmp;
        }
}

不稳定

算法分析与gap选取有关

交换排序

方法的本质：不断的交换反序的对偶，直到不再有反序的对偶为止。

两种方法：

起泡排序（Bubble sort）

快速排序（ Quick sort）

Bubble Sort

~~不是哥们,这还需要多说?~~

稳定性:最稳定的

比较次数*3是因为swapreference引入一个temp，实际上做了三次交换

Quick Sort

方法：

1）在n个对象中，取一个对象（如第一个对象——基准pivot），按该对象的关键码把所有<=该关键码的对象分划在它的左边。>该关键码的对象分划在它的右边。

2）对左边和右边（子序列）分别再用快排序。

O(nlog~2~n)

随机取中值

不太好,具体步骤可以参考下面那个

三数中值分割法

CUTOFF 是一个用于决定何时应该切换到另一种排序算法的阈值。在快速排序中，当待排序的数组或数组的一部分（子数组）变得足够小的时候，使用插入排序可能会比继续使用快速排序更高效。这是因为插入排序对于小数组具有较低的 overhead，并且可以更有效地处理已经接近有序的数据。

这里的 CUTOFF 通常是一个预先定义的常量，用于确定这个切换点。例如，如果 CUTOFF 被设置为 10，那么当子数组的大小小于或等于 10 时，算法将使用插入排序而不是快速排序。

在代码中，left + CUTOFF <= right 这个条件检查当前子数组的大小是否小于或等于 CUTOFF。如果是，那么将使用插入排序来对这部分数组进行排序。

这种策略被称为“尾递归优化”或“小数组优化”，它可以提高排序算法在处理小数据集时的性能。插入排序在数据规模较小的情况下，由于其简单性和较低的递归调用开销，往往表现得比快速排序更好。

请注意，CUTOFF 的具体值可能因实现而异，需要根据实际情况进行调整，以达到最佳的性能。在 Java 的 Arrays.sort() 方法中，就使用了类似的策略，其中快速排序和插入排序相结合，以优化不同规模数据的排序性能。

public static void quicksort(Comparable[] a){
    quicksort(a, 0, a.length() - 1);
}

public static Comparable median3(Comparable[] a, int left, int right){
    int center = (left + right) / 2;
    if(a[center].compareTo(a[left] < 0)){
        swapReferences(a, left, center);
    }
    if(a[right].compareTo(a[left]) < 0){
        swapReferences(a, left, right);
    }
    if(a[right].compareTo(a[center]) < 0){
        sWapReference(a, center, right);
    }
    swapReference(a, center, right - 1);
    return a[right - 1];
}
public static void quicksort(Comparable[] a, int left, int right){
    if(left + CUTOFF <= right){
        Comparable pivot = median3(a, left, right);
        int i = left, j = right - 1;
        while(1){
            while(a[++i].compareTo(pivot) < 0){
            }
            while(a[--j].compareTo(pivot) > 0){
            }
            if(i < j){
                swapReferences(a, i, j);
            }
            else{
                break;
            }
        }
        swapReferecens(a, i, right - 1);//把pivot还回去
        quicksort(a, left, i - 1);
        quicksort(a, i + 1, right);
    }
    else{
        insertionSort(a, left, right);
    }
    //对于什么时候用quicksort什么时候用insertionsort我存疑
}

Selection Sort

直接选择排序

public static void SelectionSort(Comparable[] a){
    for(int i = 0; i < a.length() - 1; i++){
        int k = i;
        for(int j = i + 1; j < a.length(); j++){
            if(a[j].compareTo(a[k]) < 0){
                k = j;
            }
        }
        if(k != i){
            SwapReferences(k, i);
        }
    }
}

O(n^2^)

不稳定

树形选择排序(锦标赛排序)

详情见树章节的笔记

堆排序

详情见堆章节

不稳定

Merge Sort

归并

  public static void merge( Comparable [ ] a, Comparable [ ] tmpArray,int leftPos, int rightPos, int rightEnd ){
    int leftEnd = rightPos – 1;
    int tmpPos = leftPos;
    int numElements = rightEnd – leftPos + 1;
    while( leftPos <= leftEnd && rightPos <= rightEnd )
        if( a[ leftPos ].compareTo( a[ rightPos ] ) <= 0 )
            tmpArray[ tmpPos++ ] = a[ leftPos++ ];
    	else tmpArray[ tmpPos++ ] = a[ rightPos++ ];
    while( leftPos <= leftEnd )
        tmpArray[ tmpPos++ ] = a[ leftPos++ ];
    while( rightpos <= rightEnd)
        tmpArray[ tmpPos++] = a[ rightpos++ ];
    for( int i = 0; i < numElements; i++, rightEnd-- )
        a[ rightEnd ] = tmpArray[ rightEnd ];
}

迭代的归并排序算法

非递归

public static void MergeSort(Comparable[] a){
    Comparable[] tmp = new Comparable[MaxSize];
    int len = 1;
    while(len < a.length()){
        MergePass(a, tmp, len);
        len *= 2;
        if(len >= a.length()){
            for(int j = 0; j < a.length(); j++){
                a[i] = tmp[i];
            }
        }
        else{
            MergePass(tmp, a, len);
            len *= 2;
        }
    }
}

public static void MergePass(Comparable[] init, Comparable[] merged, int len){
    int i = 0;
    while(i + 2 * len <= init.length() - 1){
        merge(init, merged,i, i + len - 1, i + 2 * len - 1);
        i += 2 * len;
    }
    if(i + len <= init.length() - 1){
        merge(init, merged, i, i + len - 1, init.length() - 1)
    }
    else{
        for(int j = i; j < init.length(); j++){
            merged[j] = init[j];
        }
    }
};