快速排序QuickSort
template <class Item>
void quickSort (Item a[], int l, int r) {
if (r<=l)
return;
int i = partition(a, l, r);
quickSort(a, l, i-);
quickSort(a, i+, r);
} template <class Item>
int partition (Item a[], int l, int r) {
int i = l -, j = r;
Item v = a[r];
for ( ; ; ) {
while (a[++i] < v);
while (a[--j] > v)
if (j == i) break;
if (i >= j) break;
exch (a[i], a[j]);
}
exch (a[i], a[r]);
return i;
}
快速排序的思想可以用来找出数组中第k大的数
template <class Item>
Item select (Item a[], int l, int r, int k) {
if (r <= l)
return a[l];
int i = partition(a, l, r);
if (i > k)
select(a, l, i-, k);
if (i < k)
select(a, i+, r, k);
}
归并排序MergeSort
数组实现
template <class Item>
void merge(Item a[], int l, int m, int r) {
int i, j;
static Item aux[maxN];
for (i = m; i>=l; i--)
aux[i] = a[i];
for (j = m; j<r; j++)
aux[r+m-j] = a[j+];
for (int k = l; k<=r; k++) {
if (aux[j] < aux[i])
a[k] = aux[j--];
else
a[k] = aux[i++];
}
} template <class Item>
void mergeSort (Item a[], int l, int r) {
if (r <= l)
return;
int m = (r+l) / ;
mergeSort(a, l, m);
mergeSort(a, m+, r);
merge(a, l, m, r);
}
链表实现
link merge (link a, link b) {
node dummy();
link head = &dummy, c = head;
while ((a!=) && (b!=)) {
if (a->item < b->item) {
c->next = a;
c = a;
a = a->next;
}
else {
c->next = b;
c = b;
b = b->next;
}
}
c->next = (a==) ? b : a;
return head->next;
}
link mergeSort (link c) {
if (c== || c->next==)
return c;
link a = c, b = c->next;
while ((b!=) && (b->next!=)) {
c = c->next;
b = b->next->next;
}
return merge (mergeSort(a), mergeSort(b));
}
堆排序HeapSort
template <class Item>
void fixDown (Item a[], int k, int n) {
while (*k+ < n) {
int child = *k + ;
if ((child+<n) && (a[child]<a[child+])
child++;
if (a[k] < a[child]) {
exch(a[k], a[child]);
k = child;
}
else
return;
} template <class Item>
void heapSort (Item a[], int n) {
int k;
// 建堆
for (k = n/; k >= ; k--)
fixDown(a, k, n); //排序
while (n->) {
exch (a[], a[n-]);
fixDown(a, k, --n);
}
}