快速排序--C++实现

1. 简述

快速排序是一种分而治之的排序，其主要流程为。

1. 选择关键元素
2. 找到元素所在位置
3. 分成左右两个区间重复过程

2. 实现

2.1 不能理解

int QuickSort::partition_v2(int *arr, int lo, int hi)
{if ( lo == hi)return lo;int pivot = arr[lo];int i = lo;int j = hi;while ( i < j) {while ( i < j && arr[j] >= pivot)--j;arr[i] = arr[j];while ( i < j && arr[i] <= pivot )i++;arr[j] = arr[i];}arr[j] = pivot;return j;
}
void QuickSort::quick_sort_impl_v2(int *arr, int lo, int hi)
{if ( lo >= hi || hi < 0 || lo < 0)return;int pos = partition_v2(arr, lo, hi);quick_sort_impl_v2(arr, lo, pos - 1);quick_sort_impl_v2(arr,pos + 1, hi);
}

2.2 自己写的

int QuickSort::partition_v1(int *arr, int lo, int hi)
{if ( lo == hi)return lo;int pivot = arr[lo];int i = lo + 1;int j = hi;while ( i < j ){while ( i < j && arr[i] <= pivot )++i;while ( i < j && arr[j] >= pivot )--j;if ( i < j ) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}}int pos = j;if ( arr[pos] > pivot)--pos;arr[lo] = arr[pos];arr[pos] = pivot;return pos;
}
void QuickSort::quick_sort_impl_v2(int *arr, int lo, int hi)
{if ( lo >= hi || hi < 0 || lo < 0)return;int pos = partition_v2(arr, lo, hi);quick_sort_impl_v2(arr, lo, pos - 1);quick_sort_impl_v2(arr,pos + 1, hi);
}

2.3 算法导论版

int QuickSort::partition_v3(int *arr, int lo, int hi)
{int pivot = arr[hi];int i = lo - 1;for ( int j = lo;j < hi; ++j) {if ( arr[j] < pivot) {i++;std::swap(arr[i], arr[j]);}}std::swap(arr[hi],arr[i + 1]);return i + 1;
}void QuickSort::quick_sort_impl_v3(int *arr, int lo, int hi)
{if ( lo >= hi || hi < 0 || lo < 0)return;int pos = partition_v3(arr, lo, hi);quick_sort_impl_v2(arr, lo, pos - 1);quick_sort_impl_v2(arr,pos + 1, hi);
}