[演算法]淺談 排序 (cont.)

int main()
{
 int arr[] = {1,5,2,6,7,8,9,4,10,14,52,99,47,100,199,222222,11,23};
 int length = sizeof(arr)/sizeof(int);

 cout << "before selection sort:" << endl;
 for(int i=0; i < length; i++)
  cout << arr[i] << " ";
 cout << endl;
 insertionSort(arr, length);
 //selectionSort(arr, length);
 //bubbleSort(arr, length);
 //quickSort(arr, 0, length);
 cout << "after selection sort:" << endl;
 for(int i=0; i < length; i++)
  cout << arr[i] << " ";
 cout << endl;
 system("pause");
 return 0;
}

先處理swapfunction

void swap(int* a, int* b) {
 int temp = *a;
 *a = *b;
 *b = temp;
}

氣泡排序法(Bubble sort)

void bubbleSort(int* arr, int length)
{
  for(int i=0; i < length-1; i++) {
   for(int j=1; j < length; j++) {
    if(arr[j-1] > arr[j]) {
     swap( &arr[j-1], &arr[j] );
    } else
     continue;
   }
  }
}

插入排序法(Insertion sort)

void insertionSort(int* arr, int length)
{
 for(int i=1; i<length; i++) {
  int temp = arr[i], index = i;
  for(int j=i-1; j>=0 && arr[j] > temp; j--) {
   arr[j+1] = arr[j];
   index = j;
  }
  arr[index] = temp;
 }
}

選擇排序法(Selection sort)

void selectionSort(int* arr, int length)
{
 for(int i=0; i<length; i++) {
  int index = i, min=arr[i];
  for(int j=i+1; j<length; j++) {
   if(arr[j] < min) {
    index = j;
    min=arr[j];
   }
  }
  if(index != i)
   swap(&arr[i], &arr[index]);
 }
}

快速排序法(Quick sort)

void quickSort(int* arr, int left, int right)
{
 int lpt, rpt, pvt;
 if( left < right ) {
  lpt = left + 1;
  rpt = right;
  pvt = arr[left];
  while( lpt <= rpt ) {
   while( arr[lpt] < pvt )
    lpt++;
   while( arr[rpt] > pvt )
    rpt--;
   if( lpt < rpt )
    swap( &arr[lpt], &arr[rpt] );
  }
   swap( &arr[left], &arr[rpt] );
   for(int p=0; p<sizeof(arr)/sizeof(int); p++)
    printf("sorting:%d\n",arr[p]);
   printf("\n");
   quickSort( arr, left, rpt-1 );
   quickSort( arr, rpt+1, right);
 }
}