0%

Sort,排序算法总结

排序算法总结

详细参考链接,寒小阳CSDN

快速排序

介绍:主要就是partition过程。

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
quickSort(int arr[], int left,int right)  
{
if(left < right)
{
int mid = partition(arr,left,right);
quickSort(arr,left,mid-1);
quickSort(arr,mid+1,right);
}
}

int partition(int arr[],int left, int right)
{
if(right <= left)
return left;
int key = arr[left];
while(left < right)
{
while(arr[right] > key) right--;
arr[right] = arr[left];
while(arr[left] < key) left++
arr[left] = arr[right];
}
arr[left] = key;
return left;
}

归并排序

介绍:利用二分法,插入排序。

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
void MSort(arr[], arr_res[],int left,int right)
{
if(left == right)
arr_res[left] = arr[left];
int mid = (left + right) / 2;
MSort(arr,arr_res,left,mid);
MSort(arr,arr_res,mid+1,right);
Merge(arr,arr_res,left,mid,right);
}

void Merge(int arr[],int arr_res[],int left,int mid,int right)
{
for(int i = left,k = left,j = mid+1; i <=mid && j<= right;k++)
{
if(arr[i] < arr[j])
arr_res[k] = arr[i++];
else
arr_res[k] = arr[j++];
}
if(i < left)
arr_res[k...] = arr[i...];
if(j < right)
arr_res[k...] = arr[j...];
return;
}

简单选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void selectSort(int arr[],int length)
{
for(int i = 0; i< length - 1 ;i++)
{
int minIndex = i;
for(int j = i+1;j< length;j++)
{
if(arr[j] < arr[minIndex])
j = minIndex;
}
if(minIndex != i)
{
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void bubbleSort(int arr[],int length)
{
for(int i = 0; i< length-1;i++)
{
for(int j = 1;j < length - i;j++)
{
if(arr[j] > arr[j-1])
{
int temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
}
}
}
}

排序算法时间空间复杂度总结