排序的概念和分类
排序是计算机程序设计中的一种重要操作,它的功能是将一个数据元素的任意序列重新排列一个按关键字有序的序列。
能够使任何数值相等的元素,排序以后相对次序不变的排序是稳定的排序,否则即是非稳定的排序。
由于待排序的记录数量不同,使得排序过程中涉及的存储器不同,可以将排序方法分为两类:内部排序指的是待排序记录存放在计算机随机存储器中进行的排序过程;外部排序指的是待排序记录的数量很大,以致内存一次不能容纳全部记录,在排序过程中尚需对外进行访问的排序过程。本文只讨论内部排序。
根据排序过程中依据的不同原则,大致可以分为插入排序、交换排序、选择排序、归并排序和计数排序等五类
根据排序过程所需工作量,可分为简单的排序方法,时间复杂度为$O(n^2)$;先进的排序方法,其时间复杂度为$O(n\log n)$;基数排序,其时间复杂度为$O(d\cdot n)$。
插入排序
直接插入排序
思想:
将一个数插入一个已经排好序的数据中。
- 第一次循环时,从第2个数开始处理。我们将第1个数作为已经排好序的数据:当第2个数 > 第1个数时,将第2个数放在第1个数后面一个位置;否则,将第2个数放在第1个数前面。此时,前两个数形成了一个有序的数据。
- 第二次循环时,我们处理第3个数。此时,前两个数形成了一个有序的数据:首先比较第3个数和第2个数,当第3个数 > 第2个数时,将第3个数放在第2个数后面一个位置并结束此次循环;否则,再和第1个数比较。如果第3个数 > 第1个数,则将第3个数插入第1个数和第2个数中间;否则,第3个数 < 第1个数,则将第3个数放在第1个数前面。此时,前三个数形成了一个有序的数据。
- 后续的数据同理处理,直至结束。
void directInsertSort(int arr[],int n){
int i,j,temp;
for(i=1;i=0&&arr[j]>temp;j--)
{
arr[j+1]=arr[j];//向右平移
}
arr[j+1]=temp;
}
}
另一种思路,通过交换的方式进行插入
void directInsertSort(int arr[],int NUM){
for (int k = 1; k < NUM; k++)
{
for (int i = k; i > 0; i--)
{
if (arr[i] < arr[i - 1])
{
arr[i] = arr[i] ^ arr[i - 1];
arr[i - 1] = arr[i] ^ arr[i - 1];
arr[i] = arr[i] ^ arr[i - 1];
}//依次交换
}
}
}
折半插入排序
折半插入排序是对直接插入排序的一种改良方式,在直接插入排序中,每次向已排序序列中插入元素时,都要去寻找插入元素的合适位置,但是这个过程是从已排序序列的最后开始逐一去比较大小的,这其实很是浪费,因为每比较一次紧接着就是元素的移动。折半排序就是通过折半的方式去找到合适的位置,然后一次性进行移动,为插入的元素腾出位置。
void halfInsertSort(int arr[],int n){
int temp;
for(int i=1;i=low){
int mid=(low+high)/2;
if(arr[mid]>temp)
high=mid-1;
else
low=mid+1;
}
for(int j=i-1;j>high;j--){
arr[j+1]=arr[j];
}
arr[high+1]=temp;
}
}
2-路插入排序
思路:
构建一相同大小的循环数组b,把原数组的元素依次插入,最后按合适次序赋值回原数组。如何实现循环呢?有办法的。可参考约瑟夫问题的数组解法中是如何实现的。
把原数组的第一个值a[0]复制过去,b[0]=a[0],作为循环数组的第一个数。当然,也可选择其它的数作为第一个数。
若a[i]=b[last],则变化last:last++(注意这里没必要这样写:last=(last+1)%n),b[last]=a[i]
若b[first]<=a[i]<b[last],则选择适当的策略,插入下图中的一路位置。
这里的二路是什么意思?没有看到哪里解释过,我的理解是,看下图:
上图中,first指向已拍好序列的第一个,last指向已排好序列的最后一个。如果按从小到大排序,first指向最小,last指向最大的。如果某一个数据a,且b[first]<=a<b[last],则a应插入图中一路所示的位置,其它的应插入二路。也就是说,可以插入的位置总的分为两路-二路插入。
void InsertSort2(int a[], int n) //二路插入
{
int first, last;
first = last = 0;
int *b = new int[n];
b[0] = a[0];
for (int i = 1; i < n; i++)
{
if (a[i] < b[first])
{
first = (first - 1 + n) % n; //first的变化必须这样写
b[first] = a[i];
}
else if (a[i] >= b[last])
{
last++; //有的人这样写:last=(last+1)%n,其实没必要,last是不会超过n-1的。
b[last] = a[i];
}
else
{
int k;
for (k = last+1; a[i] < b[(k-1+n)%n]; k=(k-1+n)%n) // 使用直接插入
b[k] = b[(k - 1 + n)%n];
b[k] = a[i];
last++;
}
}
for (int i = 0; i < n; i++)
a[i] = b[(i + first) % n];
delete[]b;
}
void InsertSort2(int a[], int n) //二路折半插入
{
int first, last;
first = last = 0;
int *b = new int[n];
b[0] = a[0];
for (int i = 1; i < n; i++)
{
if (a[i] < b[first])
{
first = (first - 1 + n) % n;
b[first] = a[i];
}
else if (a[i]>=b[last])
{
last++;
b[last] = a[i];
}
else
{
int low, high, mid, d;
low = first, high = last;
while (low != high) //折半查找
{
d = (high-low+n) % n; //元素个数
mid = (low + d / 2) % n; //中间位置
if (a[i] < b[mid])
high = mid;
else
low = (mid + 1) % n;
}
for (int k = last + 1; k != low; k = (k - 1 + n) % n) //移动元素
b[k] = b[(k - 1 + n) % n];
b[low] = a[i];
last++;
}
}
for (int i = 0; i < n; i++)
a[i] = b[(i + first) % n];
delete[]b;
}