数据排序
数据获取后，要对所得的数据进行简单加工处理，使原本杂乱的数据变得有序，便于后续的利用。
选择排序
基本思想：从未排序的数据中挑出一个最大的（或最小的）数据，后将其放到数列的最前端，重复该操作，最终得到排好序的数列。
稳定性：不稳定（即非相邻两个数据间的交换会改变相同数据的先后关系）
时间复杂度：O(n2)（即一组个数为n的数据，排序的主体操作进行的次数要达n的平方次）
空间复杂度：O(1)（即除了储存数据所用的空间外，无需其他辅助空间）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
void selection(int a[])
{
int temp = 0;
for (int i=1; i<n; i++) //最小值存放的位置
{
int k = i; //当前最小值
for (int j=i+1; j<=n; j++)
if (a[j] < a[k]) k = j;
if (k != i) //交换过程
{
temp = a[i];
a[i] = a[k];
a[k] = temp;
}
}
}
|
冒泡排序
基本思想：从数组中的第一个数开始，将其与后一个数进行比较，若后一个数比前一个数小（或大），就将两个数进行交换。经过n次遍历后，即可得到数据从小到大（或从大到小）排列的数组。
排序的优化：若其中一次遍历结束后，数组中的数没有发生交换，说明排序提前完成，此时可中断排序，节省时间。
稳定性：稳定
时间复杂度：O(n2)
空间复杂度：O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
void bubble(int a[])
{
bool ok;
for (int i=n; i>1; i--)
{
ok = false; //判断是否发生过交换
for (int j=1; j<i; j++)
{
if (a[j] > a[j+1])
{
swap(a[j],a[j+1]);
ok = true;
}
}
if (ok == false) break; //若该次循环内没有发生交换，则排序完成，无需继续循环。
}
}
|
快速排序
基本思想：快速排序是对冒泡排序的进一步优化。通过一趟排序，先将当前数组分割成两部分，一部分比记录的关键字（一般为该数组的中间一个数据）小，另一部分反之，而后再次对获得的两个部分分别进行再一次排序，直到分割的两部分数据中均只剩一个数据，则排序结束。
稳定性：不稳定
时间复杂度：O(nlogn),最差情况下会突变为O(n2)
空间复杂度：O(logn)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
void quick(int l,int r,int a[])
{
int i,j,temp,mid;
i = l;
j = r;
mid = a[(i+j)/2];
do
{
while (a[i] < mid) i++;
while (a[j] > mid) j--;
if (i <= j)
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
i++;
j--;
}
}while (i <= j);
if (j > l) quick(1,j,dt);
if (i < r) quick(i,n,dt);
}
|
插入排序
基本思想：在数据读入的过程中，每读入一个数据，就进行一次遍历，将其放置于合适的位置中，这样数据输入完成后，数组中的数便是有序的。这种操作类似于斗地主时有的人习惯抓一张牌，整一张牌。
稳定性：稳定
时间复杂度：O(n2)
空间复杂度：O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
void insertion(int a[])
{
for (int i=1; i<=n; i++)
{
int key = a[i];
int j = i-1;
while (j>0 && a[j] > key)
{
a[j+1] = a[j];
j--;
}
a[j+1] = key;
}
}
|
桶排序
基本思想：若数据存在明显的范围，那我们可以提前准备好若干个有序桶，输入数据后将其装入对应的桶中。后顺序输出各桶所对应的值（根据桶中所装数据的个数）。该排序方法对于查重有着极佳的应用性。缺点也很明显，就是必须知道数据的范围。
稳定性：不稳定
时间复杂度：O(n)
空间复杂度：O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
const int num = 10010;
const int radius = 101; //桶的范围或个数
int dt[num],buc[radius];
int n;
void bucket_init(int a[])
{
for (int i=1; i<=n; i++)
{
scanf("%d",&a[i]);
buc[a[i]]++;
}
}
void bucket_print(int a[])
{
for (int i=0; i<radius; i++) //小心i要小于radius，若桶有101个，则桶上的数值为0-100
{
while (buc[i] > 0)
{
printf("%d ",i);
buc[i]--;
}
}
cout<<endl;
}
|
归并排序
基本思想：该算法采用了分治法，即要处理一个整体，先将整体拆分成多个部分，将各个部分分别处理后，在进行合并，最终得到所要的结果。要处理一个无序数组，将其均分为两个子序列，而后对子序列分别再均分，直到得到的子序列中仅剩一个元素，而后回溯进行排序，合并，最终得到有序的目标数列。
稳定性：稳定
时间复杂度：O(nlogn)
空间复杂度：O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
void merge(int l,int r,int a[])
{
if (l >= r) return;
int mid = (l+r) / 2;
merge(l,mid,a);
merge(mid+1,r,a); //注意右半部分的开始为mid+1
int i = l;
int j = mid + 1;
int k = l;
while (i <= mid && j <= r)
{
if (a[i] <= a[j])
temp[k++] = a[i++];
else
temp[k++] = a[j++];
}
while (i <= mid) //复制左序列剩余
temp[k++] = a[i++];
while (j <= r) //复制右序列剩余
temp[k++] = a[j++];
for (int i=l; i<=r; i++) //记得复制回原数列
a[i] = temp[i];
}
|
拓展应用：求数组中逆数对的个数
逆数对：数组中数a排在数b的前面，但a>b，那么我们将(a,b)称为一个逆数对
基本思想：假定排序过程中左数列为{4，6，8，11}，右数列为{2，3，7，9}，若右数列中的2小于左数列中的4，那么它一定与左数列中在4之后（包括4）的数构成逆数对，这样的话在排序过程中避免了一对一对的统计，从而大大提高了效率。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
void merge(int l,int r,int a[])
{
if (l >= r) return;
int mid = (l+r) / 2;
merge(l,mid,a);
merge(mid+1,r,a);
int i = l;
int j = mid + 1;
int k = l;
while (i <= mid && j <= r)
{
if (a[i] <= a[j])
temp[k++] = a[i++];
else
{
temp[k++] = a[j++];
ans += mid - i + 1; //ans用于记录逆数对的个数
}
}
while (i <= mid)
temp[k++] = a[i++];
while (j <= r)
temp[k++] = a[j++];
for (int i=l; i<=r; i++)
a[i] = temp[i];
}
|