/*
冒泡排序:
外层循环n-1次
时间复杂度o(n^2)
稳定的排序
*/
void BubbleSort(int a[], int n)
{
for (int i=1; i
i-1; --j)
{
if (a[j] < a[j-1])
{
exchange = true;
swap(a[j], a[j-1]);
}
}
//如果此轮没有值交换,则说明已经排好
if (!exchange)
{
break;
}
}
cout << "冒泡排序:"<=1)个元素时,前面的v[0], v[1], ..., v[i-1]已经排好序。
用v[i]的值与v[i-1], v[i-2]...的值进行比较, 找到插入位置即将v[i]插入, 原来
位置上的元素向后顺移
时间复杂度:O(n^2)
稳定的排序
*/
void InsertSort(int a[], int n)
{
for (int i=1; i=0; --j)
{
if (tmp < a[j])
{
a[j+1] = a[j];
pos = j;
}
}
a[pos] = tmp;
}
cout << "直接插入排序:"<=low; --k)
{
swap(a[k+1], a[k]);
}
a[low] = tmp;
}
cout << "折半插入排序:"<=0; j=j-gap)
{
if (tmp < a[j])
{
a[j+gap] = a[j];
pos = j;
}
}
a[pos] = tmp;
}
}while(gap > 1);
cout << "shell排序:"<
方法
快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载
。
时间复杂度:
不稳定的排序
*/
int Partition(int a[], const int low, const int high)
{
int pivot = a[low];
int pivotpos = low;
for (int i=low+1; i<= high; ++i)
{
if (a[i] < pivot)
{
pivotpos++;
if (pivotpos != i)
{
swap(a[i], a[pivotpos]);
}
}
}
a[low] = a[pivotpos];
a[pivotpos] = pivot;
return pivotpos;
}
void QuickSort(int a[], int low, int high)
{
if (low < high)
{
int pivotpos = Partition(a, low, high);
QuickSort(a, low, pivotpos-1);
QuickSort(a, pivotpos+1, high);
}
cout << "快速排序:"<= right)
{
return ;
}
int mid = (left + right)/2;
MergeSort(a, b, left, mid);
MergeSort(a, b, mid+1, right);
Merge(a, b, left, mid, right);
}
int _tmain(int argc, _TCHAR* argv[])
{
int a[] = {2, 3, 1, 9, 8, 3};
int b[6];
MergeSort(a, b, 0, 5);
SelectSort(a, 6);
QuickSort(a, 0, 5);
ShellSort(a, 6);
BinaryInsertSort(a, 6);
InsertSort(a, 6);
BubbleSort(a, 6);
return 0;
}