#include <iostream>
using namespace std;
void printArray(int *arr, int size)
{
for(int i=0; i<size; ++i)
{
cout<< arr[i]<< ' ';
}
cout<<endl;
}
int partition(int array[], int high, int low)
{
int pivot = array[high];
while (low < high) {
while (low < high && array[low] <= pivot ) {
low++;
}
array[high] = array[low];
// printArray(array, 7);
while (low < high && array[high] >= pivot ) {
high--;
}
array[low] = array[high];
// printArray(array, 7);
}
array[low] = pivot;
// cout<<"pos:"<<low<<endl;
return low;
}
void qsort_c(int array[], int high, int low)
{
if(low >= high)
return ;
int pos = partition(array, high, low);
qsort_c(array, high, pos+1);
qsort_c(array, pos-1, low);
}
void quick_sort(int array[], int size)
{
qsort_c(array, size-1, 0);
}
int main()
{
int array[7] = {10, -22, 211, 120, -2, 23, 120};
int size = sizeof (array) / sizeof (*array);
printArray(array, size);
// partition(array, size-1, 0);
quick_sort(array, size);
printArray(array, size);
return 0;
}
#include <iostream>
using namespace std;
void PutArray(int *array, int size) {
// cout << " Array:";
for (int i = 0; i < size; ++i) {
cout << array[i] << " ";
}
cout << endl;
}
int partition(int *array, int high, int low) {
int pivot = array[low];
while (low < high) {
/*
*
* 1、low<high的条件不能去掉，在移动low和high的时候随时可能终止，跳出循环
* 2、pivot <= 中的= 不能去掉，不然两个23归位时指针不移动了，可能出现死循环 Array:0 -22 23 23 640 241 50
*
*/
while ((low < high) && pivot <= array[high]) //
high--;
swap(array[low], array[high]);
#if 0
cout << "<==:" << "low:" << low << "high:" << high;
PutArray(array, 7);
#endif
while ((low < high) && pivot >= array[low])
low++;
swap(array[low], array[high]);
#if 0
cout << "==>:" << "low:" << low << "high:" << high;
PutArray(array, 7);
#endif
}
// cout << "pos:" << low << endl;
return low;
}
void QSort(int array[], int high, int low) {
if (low < high) {
int pos = partition(array, high, low);
QSort(array, pos - 1, low);
QSort(array, high, pos + 1);
}
}
void QuickSort(int array[], int size) {
QSort(array, size - 1, 0);
}
int main() {
int array[7] = {23, -22, 241, 23, 640, 0, 50};
// int array[2] = {23, -22};
int size = sizeof(array) / sizeof(*array);
PutArray(array, size);
// InsertionSort(array, size);
// ShellSort(array, size);
// QuickSort_2(array, size);
// partition(array, size, 0);
QuickSort(array, size);
PutArray(array, size);
return 0;
}
void QuickSort_2(int array[], int size) {
int lower_list_len = 0;
int pivot = array[size - 1];
if (size <= 1) {
return;
}
for (int i = 0; i < size; ++i) {
if (array[i] < pivot) {
swap(array[i], array[lower_list_len]);
lower_list_len++;
}
}
// cout << "low:" << lower_list_len << endl;
int high_list_len = size - lower_list_len - 1;
array[size - 1] = array[lower_list_len];
array[lower_list_len] = pivot;
// cout << "high_list_len:" << high_list_len << endl;
QuickSort_2(array, lower_list_len);
QuickSort_2(&array[lower_list_len + 1], high_list_len);
}
#include <QCoreApplication>
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;
auto put = [](vector<int> &array){
std::copy(array.begin(), array.end(), ostream_iterator<int>(cout , " "));
std::cout << std::endl;
};
int partition_1(vector<int> &v, int head, int tail)
{
int pivot = v.at(head);
int i = head + 1;
int j = head;
for (;i<=tail;i++)
{
if(v.at(i) < pivot)
{
std::swap(v.at(i),v.at(++j));
}
}
std::swap(v.at(head),v.at(j));
return j;
}
int partition_2(vector<int> &v, int head, int tail)
{
int pivot = v.at(head);
int i = head + 1;
int j = tail;
for (;i <= j;)
{
while (i <= j && v.at(j) >= pivot)
j--;
while (i <= j && v.at(i) <= pivot)
i++;
if(i <= j)
{
std::swap(v.at(i),v.at(j));
}
}
cout << head << ":";
std::swap(v.at(head),v.at(j));
put(v);
return j;
}
int partition(vector<int> &array, int low, int high)
{
int pivot = array[high];
while (low < high) {
while (low < high && array[low] <= pivot ) {
low++;
}
array[high] = array[low];
// printArray(array, 7);
while (low < high && array[high] >= pivot ) {
high--;
}
array[low] = array[high];
// printArray(array, 7);
}
array[low] = pivot;
// cout<<"pos:"<<low<<endl;
return low;
}
void qSort(vector<int> &v, int head, int tail)
{
if(head > tail)
return ;
int piovt = partition(v, head, tail);
qSort(v, head, piovt - 1);
qSort(v, piovt + 1, tail);
}
int main(int argc, char *argv[])
{
int a[] = {1, 12, 3, 44, -5};
int s = sizeof(a) / sizeof(int);
vector<int> array(a, a + s);
qSort(array, 0, array.size()-1);
put(array);
return 0;
}
#if 0
int main(int argc, char *argv[])
{
QCoreApplication core(argc, argv);
//for(int i=0; i<)
int a[] = {1, 12, 3, 44, -5};
int s = sizeof(a) / sizeof(int);
vector<int> array(a, a + s);
auto put = [](vector<int> &array){
std::copy(array.begin(), array.end(), ostream_iterator<int>(cout , " "));
std::cout << std::endl;
};
//std::copy(array.begin(), array.end(), ostream_iterator<int>(cout , " "));
int size = array.size() - 1;
int flag = true;
for (size_t i = 0; flag ; i++)
{
flag = false;
for (size_t j = size; j > i; j--)
{
if (array[j] < array[j-1])
{
std::swap(array[j], array[j-1]);
flag = true;
}
}
cout << "i:" << i << " ";
put(array);
}
put(array);
return core.exec();
}
#endif
备份地址: 【O(nLogn)排序 ：快速】