algorithms.cpp

选择排序

#include "StdAfx.h"
#include "Algorithms.h"

void inssort (int A[], int n){  // Insertion Sort
/*	for (int i=1; i < n; i++)  // Insert i'th record
		for (int j = i; (j>0) && (A[j] < A[j-1]); j--)
			swap(A, j, j-1);
			*/
	for (int i = 1; i < n; i++){
		for (int j = i; j > 0; j--){
			if (A[j - 1] > A[j]) swap(A, j, j-1);
		}
	}
}

void bubsort (int A[], int n){  // Bubble Sort
	for (int i=0; i < n-1; i++)  // Bubble up i'th record
		for (int j = n-1; j>i; j--)
			if (A[j] < A[j-1])
				swap(A, j, j-1);
}

void selsort (int A[], int n){  // Selection Sort
	for (int i = 0; i < n-1; i++){  // Select i'th record
		int lowindex = i;   // Remember its index
		for (int j = n-1; j>i; j--)  // Find the least value
			if (A[lowindex] > A[j])
				lowindex = j;  // Put it in place
			swap(A, i, lowindex);
	}
}

int findpivot(int A[], int i, int j)
  { return (i+j) / 2; }

int partition(int A[], int l, int r, int& pivot) {
  do {             // Move the bounds inward until they meet
    while ((A[++l] < pivot));     // Move l right and
    while ((r != 0) && (A[--r] > pivot)); // r left
    swap(A, l, r);              // Swap out-of-place values
  } while (l < r);              // Stop when they cross
  swap(A, l, r);                // Reverse last, wasted swap
  return l;      // Return first position in right partition
}

void qsort(int A[], int i, int j) { // Quicksort
  if (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 subarray
  int k = partition(A, i-1, j, A[j]);
  swap(A, k, j);             // Put pivot in place
  qsort(A, i, k-1);
  qsort(A, k+1, j);
}

void qsort(int A[], int i) {
	qsort(A, 0, i - 1);
}

void sort(int* array, int n) {
  qsort(array, 0, n-1);
}

void swap(int B[],int a, int b){
	int c;
	c=B[a];
	B[a]=B[b];
	B[b]=c;
}