0%

算法分析复习笔记-排序

算法分析课程复习笔记 - 排序

冒泡排序

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
#include<iostream>

using namespace std;

int main(){
int data[8] = {50,13,55,97,27,38,49,65};
int exchange = 1;
while(exchange){
exchange = 0;
for (int j = 0; j < 8 - 1; j++) {
if( data[j] > data[j+1]){
int temp = data[j+1];
data[j+1] = data[j];
data[j] = temp;
exchange = 1;
}
}
for (int i = 0; i < 8; i++) {
cout<<data[i]<<" ";
}
cout<<endl;
}
for (int i = 0; i < 8; i++) {
cout<<data[i]<<" ";
}
cout<<endl;
return 0;
}

二路归并排序 JAVA

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
import java.util.Arrays;

public class MergeSort {

public static void main(String[] args) {
int[] array = {9,10,21,3,6,22,21,33};
mergeSort(array,0,array.length - 1,new int[array.length]);
System.out.println(Arrays.toString(array));
}

public static void mergeSort(int[] array , int left , int right,int[] temp) {
if( left < right ) {
int center = (left + right) / 2;
mergeSort(array,left,center,temp);
mergeSort(array,center+1,right,temp);
merge(array,left,center,right,temp);
}
}

public static void merge(int[] array , int left , int center , int right, int[] temp) {
int currentLeft = left;
int currentRight = center + 1;
int tempArrayPos = currentLeft;
while(currentLeft <= center && currentRight <= right) {
if(array[currentLeft] <= array[currentRight]) {
temp[tempArrayPos ++ ] = array[currentLeft++];
}else {
temp[tempArrayPos++ ] = array[currentRight++];
}
}

while( currentLeft <= center ) {
temp[tempArrayPos ++ ] = array[currentLeft++];
}

while(currentRight <= right) {
temp[tempArrayPos++ ] = array[currentRight++];
}

for(int i = left ; i <= right ; i ++ ) {
array[i] = temp[i];
}

}

}

快速排序

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 qsort(int begin,int end,int nums[]){
if(begin < end){
int left = begin;
int right = end;
int flag = nums[begin];
while(left<right){
while(left < right && nums[right] >= flag){
right --;
}
if(left<right){
nums[left++] = nums[right];
}
while(left<right && nums[left] < flag){
left ++;
}
if(left<right){
nums[right--] = nums[left];
}
}
nums[left]=flag;
qsort(begin,left-1,nums);
qsort(left+1,end,nums);
}
}