选择,插入,归并,快速排序总结

一,O(n^2)选择排序和插入排序

1选择排序
基本思路:标记第一个数,循环找到比这数小的然后对换,直至找到数组中最小的数,最好将最小的数放入标记的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void selectSort(int arr[],int n)
{
for(int i=1;i<n;i++)
{
int minIndex=i;
//遍历i+1到n数,找到最小值
for(int j=i+1;j<n;j++)
{
if(arr[j]<arr[minIndex])
minIndex=j;
}
swap(arr[j],arr[minIndex]);
}
}

2,插入排序
基本思路:从i开始,与i-1进行对比,插入排序不需要进行全循环,而是可以中途退出,判断的是从最后到第一的大小关系。

第一种方法

1
2
3
4
5
6
7
8
9
10
11
12
13
void InsertSort(int arr[],int n)
{
for(int i=1;i<n;i++)
{
for(j=i;j>0;j--)
{
if(arr[j]<arr[j-1])
swap(arr[j],arr[j-1])
else
break;
}
}
}

第二 相比第一种方法。不再需要两两交换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void InsertSort(int arr[],int n)
{

int j;
for(int i=1;i<n;i++)
{
int t=arr[i];
for(j=i;j>0;j--)
{
if(arr[j-1]>t)
arr[j]=arr[j-1];
}
arr[j]=t; //找到t所处在位置,并赋值.
}
}

三,归并排序(nlogn)
基本思路:需要一个暂存区aux,然后范围为l到r,i和j分别为左右两边需要比较的值,k为通过比较之后,符合的数值存放位置。,实际与二分法思维相符

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
//归并排序
void merageSort(int arr[],int n)
{
_merageSort(arr,0,n-1);
}

void _merageSort(int arr[],int l,int r)
{
if(l>=r)
return;
int mid=(l+r)/2;
_merageSort(arr,int l,int mid);
_merageSort(arr,int mid+1,int r);
_merage(arr,l,mid,r);
}

void _merage(int arr[],int l,int mid,int r)
{ int aux[l-r+1];
for(int i=l;i<=r;i++)
{
aux[i-1]=arr[i];
}

int i=l;j=mid+1;
for(int k=l;k<=r;k++)
{
if(i>mid)
{
aux[k]=aux[j-l];
i++;
}

else if(j>r)
{
aux[k]=aux[i-l];
j++;
}
else if(aux[i-l]<aux[j-l])
aux[k]=aux[i-l];
else
aux[k]=aux[j-l];
}

}

四.快速排序(nlogn)
基本思路:选择一个数作为中间数t,递归整个数据,比t大的放在右边,比t小的放在左边

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
void QuickSort(int arr[],int n)
{
_QuickSort(int arr[],0,n-1)
}

void _QuickSort(int arr[],int l,int r)
{
if(l>=r)
{
return;
}

int p=_Par(arr,l,r);
_QuickSort(arr,l,p);
_QuickSort(arr,p+1,r);
}


void _Par(arr,l,r)
{
int v=arr[l];
int j=l;
for(int i=l+1;i<=r;i++)
{
if(arr[i]<v)
{
j++;
swap(arr[j],arr[i]);
}
swap(arr[l],arr[j]);
}

return j;
}

2.二路快排

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void _par(arr,l,r)
{
\\随机化生成标定点point
swap(arr[l],arr[rand()%(r-l+1)+1]);
int v= arr[l];
int i=l+1;int j=r;
while(true)
{
while(i<=r && arr[i]<v)
i++;
while(j>=l+1 && arr[j]>v)
j--;
if(i>j)
break;
swap(arr[i],arr[j])
i++;
j--;
}
swap(arr[l],arr[j]);
return j;
}

3三路快排

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void _quick3ways(arr,l,r)
{
int v=arr[l];
int lt=l;int gt=r+1;int i=l+1;
while(i<gt)
{
if(arr[i]<v){
swap(arr[i],arr[lt+1]);
i++;
lt++;
}
else if(arr[i]>v)
{
swap(arr[i],arr[gt-1])
gt--;
}
else
i++;
}
swap(arr[l],arr[lt]);

_quick3ways(arr,l,lt-1);
_quick3ways(arr,gt,r);
}

文章目录
  1. 1. 第一种方法
  2. 2. 第二 相比第一种方法。不再需要两两交换。
,