数据结构作业 练习函数指针

3种排序算法就不说了，插入排序，快速排序，选择排序。

这算法我是记住了又忘记了，忘记后又要记。。。太无语了

最中要的是函数指针的用法。直接看代码.

我太郁闷了，这博客居然要把直接复制代码html会解析出错。

逼我把代码先弄成html然后再复制上来。。。

#include <vector>
#include <iostream>
#include <algorithm>
#include <time.h>
using namespace std;

typedef vector<int> ArrayInt;

typedef void (*sort_type)(ArrayInt&);
void insersion_sort(ArrayInt& arr);
void selection_sort(ArrayInt& arr);
void quick_sort(ArrayInt& arr);

int max_key(ArrayInt &arr,int low,int hight);
void recursive_quick_sort(ArrayInt& arr,int low,int hight);
int partition(ArrayInt& arr,int low,int hight);

void my_test_sort(ArrayInt& arr,sort_type p)
{
(*p)(arr);
}

void insersion_sort(ArrayInt& arr)
{
int first_unsorted;
int position;
int current;

for (first_unsorted = 1;first_unsorted < arr.size();first_unsorted++)
{
if (arr[first_unsorted] < arr[first_unsorted-1])
{
position = first_unsorted;
current = arr[first_unsorted];
do
{
arr[position] = arr[position-1];
position--;
}while(position>0 && arr[position-1] >current);

arr[position] = current;
}

}

}

void selection_sort(ArrayInt& arr)
{
for(int position = arr.size()-1;position>0;position--)
{
int max = max_key(arr,0,position);
swap(arr[max],arr[position]);
}

}

void quick_sort(ArrayInt& arr)
{
recursive_quick_sort(arr,0,arr.size()-1);
}

void recursive_quick_sort(ArrayInt& arr,int low,int hight)
{
int pivot_position;
if (low < hight)
{
pivot_position = partition(arr,low,hight);
recursive_quick_sort(arr,low,pivot_position-1);
recursive_quick_sort(arr,pivot_position+1,hight);
}
}

int partition(ArrayInt& arr,int low,int hight)
{
int iRndPivID;
srand(unsigned(time(0)));
iRndPivID = (rand() % (hight - low + 1)) + low;
swap(arr[iRndPivID], arr[hight]);
int iPivValue;
int i;
int iPivPos;
iPivValue = arr[hight];
iPivPos = low - 1;

for (i=low; i<=hight-1; i++)
{
if (arr[i] <= iPivValue)
{
iPivPos++;
swap(arr[iPivPos],arr[i]);
}
}
iPivPos++;
swap(arr[iPivPos],arr[hight]);
return iPivPos;

}
int max_key(ArrayInt &arr,int low,int hight)
{
int largest,current;
largest = low;
for(current = low+1;current<=hight;current++)
{
if (arr[largest] < arr[current])
{
largest = current;
}
}
return largest;
}

int main()
{
ArrayInt arrayInt;
int st;
cout <<"请输入排序算法\n1.插入排序\n2.选择排序\n3.快速排序\n";
cin >> st;
sort_type p = NULL;
switch(st)
{
case 1:
p = insersion_sort;
break;
case 2:
p = selection_sort;
break;

case 3:
p = quick_sort;
break;

default:
p = quick_sort;

}
cout << "请输入整数的个数后，然后输入整数"<<endl;
int n;
cin>>n;
for (int i=0;i<n;i++)
{
int num;
cin>>num;
arrayInt.push_back(num);
}
cout << "排序前的数字为:"<<endl;
for (int i=0;i<n;i++)
{
cout << arrayInt[i] << endl;
}

my_test_sort(arrayInt,p);
cout << "排序后的数字为:"<<endl;
for (int i=0;i<n;i++)
{
cout << arrayInt[i] << endl;
}

return 0;
}