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);
}
}
