数据结构第八章排序算法实现
插入排序
直接插入排序
1
2
3
4
5
6
7
8
9
10
11
12
13
|
void InsertSort(int A[],int n)
{
int j,j,temp;
for(int i = 1;i < n;i++)//所有i之前的元素为有序序列,初始第一个元素自己为有序序列
{
if(A[i-1] > A[i])//待排序的i如果大于之前的元素(有序序列最大值),不用进入处理,否则进入之前的序列进行对比处理
{
temp = A[i];//临时保存第i元素的值,因为要在前面进行插入,所以有序序列需要进行后移
for(j = i - 1;j>=0&&A[j]>temp;j--)A[j+1] = A[j];//依次向前比较,如果temp值小,需要向前比较,序列后移,跳出循环时temp要么需要在0位置插入(j=-1),要么此时的j对应的元素已经不大于temp,所以需要temp插入j+1的位置
A[j+1] = temp;
}
}
}
|
希尔排序
通过设置增量,将数组分成不同序列,子序列内部采用直接插入,增量不断减小,直到为1
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
void ShellSort(int A[],int n)
{
int d,i,j,temp;//d为增量
for(d=n/2;d>=1;d/=2)//增量初始设为数组长度一半,每次循环结束取其一半
{
for(i = d;i<n;i++)//子序列内部采用直接插入排序
{
if(A[i]<A[i-d])
{
temp = A[i];//临时保存需要插入的值,因为此位置会被前面序列后跳取代
for(j = i-d;j>=0&&A[j]>temp;j-=d)A[j+d]=A[j];//j每次向前走d个单位,若大于待插入值,值后跳
A[j+d] = temp;//出来时此位置后+d的位置需要被插入
}
}
}
}
//这个版本可能更直观,先把某一子序列整体排完,才切换下一个子序列
void ShellSort(int A[], int n)
{
int d, start, i, j, temp;
// d 为增量
for (d = n / 2; d >= 1; d /= 2)
{
// start 表示每个子序列的起点
// 一共有 d 个子序列：0,1,2,...,d-1
for (start = 0; start < d; start++)
{
// 对 A[start], A[start+d], A[start+2d]... 做直接插入排序
for (i = start + d; i < n; i += d)
{
if (A[i] < A[i - d])
{
temp = A[i];
for (j = i - d; j >= 0 && A[j] > temp; j -= d)
{
A[j + d] = A[j];
}
A[j + d] = temp;
}
}
}
}
}
|
交换排序
冒泡排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
void BubbleSort(int A[],int n)
{
int i,j,temp,flag;
for(i = 0;i<n-1;i++)//一共需要n-1轮
{
flag = 0;
for(j = 0;j<n-1-i;j++)//每轮需要n-1次再减去已经排好的个数(也等于当前轮数)
{
if(A[j]>A[j+1])
{
temp = A[j];
A[j] = A[j+1];
A[j+1] = temp;
flag = 1;//如果发生了交换,说明序列还未有序
}
}
if(!flag)break;//如果次轮没有交换,此时flag为0,说明已经有序,可以跳出循环
}
}
|
快速排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
int Partition(int A[],int low,int high)
{
int pivot = A[low];//让第一个元素为中间元素
while(low<high)
{
while(low<high&&A[high]>=pivot)high--;//从后找到比中间元素小的元素
A[low] = A[high];//换到左边low的位置
while(low<high&&A[low]<=pivot)low++;//从前找到比中间元素大的元素
A[high] = A[low];//换到右边high的位置
}
A[low] = pivot;//最后low=high,这个位置就是中间元素的位置
return low;//返回这个位置
}
void QuickSort(int A[],int low,int high)
{
if(low < high)
{
int pivotposition = Partition(A,low,high);//找个中间元素位置
QuickSort(A,low,pivotposition-1);//递归左边
QuickSort(A,pivotposition+1,high);//递归右边
}
}
|
选择排序
简单选择排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
void SelectSort(int A[],int n)
{
int i,j,temp,minIndex;
for(i = 0;i<n-1;i++)
{
minIndex = i;//当前最小值下标为i
for(j = i+1;j<n;j++)
{
if(A[j]<A[minIndex])minIndex = j;//如果当前元素小于最小值,更新最小值元素下标
}
if(minIndex!=i)//当前最小值有变化,交换元素
{
temp = A[i];
A[i] = A[minIndex];
A[minIndex] = temp;
}
}
}
|
堆排序
采用王道书写法,从下标1开始,0位置用来暂存子树根节点
这样分支节点<=n/2,左孩子为2i,右孩子为2i+1;
思路
将数组调整为大顶堆,任意根节点大于其左右子树,这样保证调整后1号位置为最大值,然后与最后元素交换,保证递增,
此时大顶堆树结构被破坏,将后面排好序的元素去除重新调整堆
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
void HeapAdjust(int A[],int k,int len)
{
A[0] = A[k];
int i;
for(i = 2*k;i<=len;i*=2)//左孩子为2k,右孩子为2k+1
{
if(i<len&&A[i]<A[i+1])i++;//比较左右子树谁值更大;
if(A[0]>=A[i])break;
//大顶堆 → 小顶堆：
//if(i<len&&A[i]>A[i+1])
//if(A[0]<=A[i])break;
else{
A[k] = A[i];
k=i;//发生调整,从此开始,继续向下调整
}
}
A[k] = A[0];//最后找到原来根的位置
}
void BuildBigHeap(int A[],int len)//分支节点为<=n/2(因为数据从1开始)
{
int i;
for(i = len/2;i>0;i--)
{
HeapAdjust(A,i,len);
}
}
void HeapSort(int A[],int len)
{
BuildBigHeap(A,len);//初始建堆
for(int i = len;i>1;i--)//执行n-1次
{
swap(A[1],A[i]);//每次把最后的元素和根节点元素互换,保证最大的在最后
HeapAdjust(A,1,i-1);//从新调整1到未排序元素之间的树;
}
}
//大顶堆 → 小顶堆：
//if(i<len&&A[i]<A[i+1]) → if(i<len&&A[i]>A[i+1])
//if(A[0]>=A[i])break; → if(A[0]<=A[i])break;
|
归并排序
思路
通过辅助数组,将待排序两个序列复制到辅助数组,通过两个指针从两个字序列开始位置向后对比,递增排序则,较小值覆盖原数组位置
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
27
28
29
30
|
int *B = (int *)malloc(n*sizeof(int));
void Merge(int A[],int low,int mid,int high)
{
int i,j,k;//i,j分别指向辅助数组里第一,二个子序列,k指向原来数组待插入位置
for(k = low;k<=high;k++)
{
B[k] = A[k];
}//先通过k复制元素到辅助数组
for(i=low,j=mid+1,k=i;i<=mid&&j<=high;k++)//选取两个子序列小值放入原数组
{
if(B[i]<=B[j])A[k]=A[i++];
else A[k] = A[j++];
}
while(i<=mid)A[k++]=A[i++];//某一个子序列完毕,将剩余一个数组放入原数组,只会循环一个
while(j<=high)A[k++]=A[j++];
}
void MergeSort(int A[],int low,int high)
{
if(low<high)
{
int mid = (low+high)/2;//当前中间元素
//int mid = low + (high - low) / 2;防溢出
MergeSort(A,low,mid);//递归进去排左边
MergeSort(A,mid+1,high);//递归进去排右边
Merge(A,low,mid,high);//归并两个子序列
//理解递归思想,第一次进去,会先层层进去到前两个元素归并
}
}
|
计数排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
void CountSort(int A[],int B[],int n,int k)//B为输出数组,n为A的长度,k为A[]的取值范围
{
int i,c[k];
for(i=0;i<n;i++)
{
C[A[i]]++;//统计出现次数
}
for(i = 1;i<k;i++)
{
C[i] = C[i] + C[i-1];//从前向后统计各位置序号位置
}
for(i = n-1;i>=0;i--)
{
C[A[i]] = C[A[i]]-1;//先得到放入位置
B[C[A[i]]] = A[i];
}
}
|
房子 收录于 考研408