Θ(n2) Sorting

Bubble Sort

从下往上逐渐把最小值浮上来，修改好的放在最上面

template <class Elem, class Comp>
void bubsort(Elem A[], int n) {for (int i=0; i<n-1; i++)for (int j=n-1; j>i; j--)if (Comp::lt(A[j], A[j-1]))swap(A, j, j-1);
}

比较次数是固定的，交换次数有极端值
$$n+(n-1)+(n-2)+...+2+1=n(n-1)/2$$

Selection Sort

减少了冒泡排序中没有意义的交换，每次选出剩余数中的最小值进行交换

template <class Elem, class Comp>
void selsort(Elem A[], int n) {for (int i=0; i<n-1; i++) {int lowindex = i; // Remember its indexfor (int j=n-1; j>i; j--) // Find leastif (Comp::lt(A[j], A[lowindex]))   lowindex = j; // Put it in placeif (lowindex != i)   swap(A, i, lowindex);}
}

Index Cheacking 的 n 是在检查是否在最后交换的元素是自己, 可以去掉

Insertion Sort

相当于从头开始每次从后面加一个元素，然后前面n个一起排序

template <class Elem, class Comp>
void inssort(Elem A[], int n) {for (int i=1; i<n; i++)for (int j=i; (j>0)&&(Comp::lt(A[j], A[j-1])); j--)swap(A, j, j-1);
}

这个优于前面两个的一点是，在最好的情况下，不用全部都比。比较平均用时被优化了一半

Shell Sort

就是再次优化insertion sort，使列表一开始就处于一个几乎排序好的状态。在这种情况下，最好的情况只需要Θ(n)

如图，对于一个有十六个元素的列表，首先八个八个考虑，对应位置交换。再四个四个考虑，对应位置两两交换。最后两个两个交换。通过范围不断缩小保证这个列表“nearly sorted”

// Modified version of Insertion Sort
template <class Elem, class Comp>
void inssort2(Elem A[], int n, int incr) {for (int i=incr; i<n; i+=incr)for (int j=i;(j>=incr) && Comp::lt(A[j], A[j-incr]));j-=incr)//相当于每次从后向前处理子列swap(A, j, j-incr);
}
template <class Elem, class Comp>
void shellsort(Elem A[], int n) { // Shellsortfor (int i=n/2; i>2; i/=2) // For each incrfor (int j=0; j<i; j++) // Sort sublistsinssort2<Elem,Comp>(&A[j], n-j, i); //inssort2<Elem,Comp>(A, n, 1);}

• 可以和insertion sort对比一下，发现变化的只有单位长度（初始值&步长）
• Select other increments (incr) may improve the performance of shell sort
• Average-case performance is $O(n^{1.5})$

Θ(nlog n) Sorting

Quick Sort

类似Binary Search Tree

通过左右指针不断向中间移动来实现每一轮排序。从列表外开始，每次向中间移动一个。定位到左指针比pivot大右指针比pivot小的时候，否则继续移动，直到左指针位置大于右指针位置。注意左指针大于右指针时也会完成交换的操作，最后还会换回来。（因为使用的是do..while）

template <class Elem, class Comp>
void qsort(Elem A[], int i, int j) { // Quicksortif (j <= i) return; // Don't sort 0 or 1 Elem int pivotindex = findpivot(A, i, j); swap(A, pivotindex, j); // Put pivot at end // k will be the first position in the right subarrayint k = partition<Elem,Comp>(A, i-1, j, A[j]); swap(A, k, j); // Put pivot in placeqsort<Elem,Comp>(A, i, k-1); qsort<Elem,Comp>(A, k+1, j);
} template <class Elem>
int findpivot(Elem A[], int i, int j){ return (i+j)/2; }template <class Elem, class Comp>
int partition(Elem A[], int l, int r, Elem& pivot) {do { // Move the bounds in until they meetwhile (Comp::lt(A[++l], pivot));while ((r != 0) && Comp::gt(A[--r], pivot));swap(A, l, r); // Swap out-of-place values} while (l < r); // Stop when they crossswap(A, l, r); // Reverse last swapreturn l; // Return first pos on right
}

• 由于l指针在指向pivot时就不符合条件了，所以不用额外判断
• 最后把右边的第一个和pivot换(右边第一个一定比pivot要大)
  

Merge Sort

两个两个分 四个四个分 最后全部一起分

template <class Elem, class Comp>
void mergesort(Elem A[], Elem temp[], int left, int right) {int mid = (left+right)/2;if (left == right) return; mergesort<Elem,Comp>(A, temp, left, mid);mergesort<Elem,Comp>(A, temp, mid+1, right);for (int i=left; i<=right; i++) // Copytemp[i] = A[i];int i1 = left; int i2 = mid + 1;for (int curr=left; curr<=right; curr++) {if (i1 == mid+1) // Left exhaustedA[curr] = temp[i2++];else if (i2 > right) // Right exhaustedA[curr] = temp[i1++];else if (Comp::lt(temp[i1], temp[i2]))A[curr] = temp[i1++];else A[curr] = temp[i2++];}
}

理解 ：

• 每次copy一次原数组，指针curr在被修改的数组上移动，指针i1和i2在copy的数组上移动。
• 指针i1和i2初始化在0和mid+1的位置(分别是这个数组中已被分好的两个小数组的起点)。
• 每次比较i1和i2所指的值
  • 如果i1比i2小，把原数组上该位置设置为这个值，i1后移。
  • 如果i2比i1小，把原数组上该位置设置为这个值，i2后移。
  • 如果i1越界，说明i2剩下那部分都比i1部分小（i1和i2所指的部分是已经排序好的），直接把i2剩下的接上。
  • 如果i2越界，同理，把i1剩下的接上

改进版（当列表长度小于4时，使用插入排序减小时间）

template <class Elem, class Comp>
void mergesort(Elem A[], Elem temp[], int left, int right) {int mid = (left+right)/2;if (left == right) return;if ((right–left) > 4){mergesort<Elem,Comp>(A, temp, left, mid);mergesort<Elem,Comp>(A, temp, mid+1, right);}else insertsort(A)for (int i=left; i<=right; i++) // Copytemp[i] = A[i];int i1 = left;int i2 = mid + 1;for (int curr=left; curr<=right; curr++) {if (i1 == mid+1) // Left exhaustedA[curr] = temp[i2++];else if (i2 > right) // Right exhaustedA[curr] = temp[i1++];else if (Comp::lt(temp[i1], temp[i2]))A[curr] = temp[i1++];else A[curr] = temp[i2++];}
}

Heap Sort

Remove (get) the MAX (root) until the heap is empty
先变成堆，然后逐渐移除最大的。

template <class Elem, class Comp>
void heapsort(Elem A[], int n) { // HeapsortElem mval;maxheap<Elem,Comp> H(A, n, n);for (int i=0; i<n; i++) // Now sortH.removemax(mval); // Put max at end
}

Bin Sort

template <class Elem>
void binsort(Elem A[], int n) {List<Elem> B[MaxKeyValue];Elem item;for (i=0; i<n; i++) B[A[i]].append(A[i]);for (i=0; i<MaxKeyValue; i++)for (B[i].setStart(); B[i].getValue(item); B[i].next())output(item);
}

n是插入操作，MaxKeyValue是输出次数

Radix Sort

先排个位 再排十位

template <class Elem, class Comp>
void radix(Elem A[], Elem B[], int n, int k, int r, int cnt[]) {// cnt[i] stores # of records in bin[i]int j;for (int i=0,rtok=1;i<k;i++,rtok*=r) {for(j=0;j<r;j++) cnt[j] = 0;// Count # of records for each binfor(j=0;j<n;j++) cnt[(A[j]/rtok)%r]++;// cnt[j] will be last slot of bin j.for(j=1; j<r;j++) cnt[j] = cnt[j-1] + cnt[j];for(j=n-1;j>=0;j--) B[--cnt[(A[j]/rtok)%r]] = A[j];for(j=0;j<n;j++) A[j] = B[j];}
}

这个没咋看懂

Empirical Comparison

quick sort还是最快的