c++クイックソートアルゴリズム
28115 ワード
#include
//
void sortMaoPao(int * array, int len)
{
for (int i = 0; i < len; i++)
{
for (int j = 0; j < len - i - 1; j++)
{
if (array[j] > array[j + 1])
{
int temp = array[j + 1];
array[j + 1] = array[j];
array[j] = temp;
}
}
}
}
void printfSort(int *array, int len)
{
for (int i = 0; i < len; i++)
{
LOGEM(" array[%d] = %d ", i, array[i]);
}
}
// ( )
void quickSort(int left, int right, vector<int>& arr)
{
if (left >= right) //
return;
if (left < 0 || right >= arr.size())
{
cout << "error args! array bound." << endl;
return;
}// ,
int i, j, base, temp;
i = left, j = right;
base = arr[left]; //
while (i < j)
{
while (arr[j] <= base && i < j)
j--;
while (arr[i] >= base && i < j)
i++;
if (i < j)
{
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
//
arr[left] = arr[i];
arr[i] = base;
quickSort(left, i - 1, arr);//
quickSort(i + 1, right, arr);//
}
// ,
int Partition(int data[], int length, int start, int end)
{
if (data == NULL || length <= 0 || start < 0 || end >= length)
{
printf("error
");
return -1;
}
int small = start - 1;
for (int i = start; i < end; i++)
{
if (data[i] < data[end])
{
small++;
if (small != i)
{
int temp = data[i];
data[i] = data[small];
data[small] = temp;
}
}
}
small++;
int temp = data[small];
data[small] = data[end];
data[end] = temp;
return small;
}
void QuickSort(int data[], int length, int start, int end)
{
if (start == end)
return;
int index = Partition(data, length, start, end);
if(index > start)
QuickSort(data, length, start, index - 1);
if(index < end)
QuickSort(data, length, index + 1, end);
}
// for
void QuickSort_while(int data[], int length, int start, int end)
{
int index = Partition(data, length, start, end);
std::vector<int> mVec;
if (index > start)
{
mVec.push_back(start);
mVec.push_back(index - 1);
}
if (index < end)
{
mVec.push_back(index + 1);
mVec.push_back(end);
}
for (int i = 0; i < mVec.size() / 2; i++)
{
int s = mVec[i * 2 + 0];
int e = mVec[i * 2 + 1];
index = Partition(data, length, s, e);
if (index > s)
{
if ((index - 1) != s)
{
mVec.push_back(s);
mVec.push_back(index - 1);
}
}
if (index < e)
{
if ((index + 1) != e)
{
mVec.push_back(index + 1);
mVec.push_back(e);
}
}
}
}
int main(int argc, char *argv[])
{
//
int array[] = { 2, 3, 4, 1, 6, 7, 8, 9 };
std::vector<int> mVecArray = { 2, 3, 4, 1, 6, 7, 8, 9, 0 ,4};
int num = 8;
//sortMaoPao(array, num);
//quickSort(0, mVecArray.size() - 1, mVecArray);
QuickSort_while(mVecArray.data(), mVecArray.size(), 0, mVecArray.size() - 1);
printfSort(mVecArray.data(), mVecArray.size());
return 0;
}