排序算法

Posted on | In | Comments: | Views:

归并排序

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
47
void Merge(int *A,int *L,int leftCount,int *R,int rightCount) {
	int i,j,k;

	i = 0; j = 0; k =0;

	while(i<leftCount && j< rightCount) {
		if(L[i]  < R[j]) A[k++] = L[i++];
		else A[k++] = R[j++];
	}
	while(i < leftCount) A[k++] = L[i++];
	while(j < rightCount) A[k++] = R[j++];
}

// Recursive function to sort an array of integers.
void MergeSort(int *A,int n) {
	int mid,i, *L, *R;
	if(n < 2) return;

	mid = n/2;  // find the mid index.


	L = new int[mid];
	R = new int [n - mid];

	for(i = 0;i<mid;i++) L[i] = A[i]; // creating left subarray
	for(i = mid;i<n;i++) R[i-mid] = A[i]; // creating right subarray

	MergeSort(L,mid);  // sorting the left subarray
	MergeSort(R,n-mid);  // sorting the right subarray
	Merge(A,L,mid,R,n-mid);  // Merging L and R into A as sorted list.

	delete [] R;
	delete [] L;
}

int main() {
	int A[] = {6,2,3,1,9,10,15,13,12,17}; // creating an array of integers.
	int i,numberOfElements;

	numberOfElements = sizeof(A)/sizeof(A[0]);

	MergeSort(A,numberOfElements);

	for(i = 0;i < numberOfElements;i++)
	   cout << " " << A[i];
	return 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
29
30
31
32
33
void QuickSort(int array[], int start, int last)
 {
     int i = start;
     int j = last;
     int temp = array[i];
     if (i < j) //如果i和j相遇则排序结束
     {
         while (i < j)
         {
             while (i < j &&  array[j]>=temp ) //从右边找比左边小的数
                 j--;
             if (i < j)
             {
                 array[i] = array[j];
                 i++;
             }

             while (i < j && temp > array[i])  //从左边找比右边大的数
                 i++;
             if (i < j)
             {
                 array[j] = array[i];
                 j--;
             }

         }
         //把基准数放到i位置
         array[i] = temp;
         //递归方法
         QuickSort(array, start, i - 1);
         QuickSort(array, i + 1, last);
     }
 }

冒泡排序

1
2
3
4
5
6
7
8
void bubble_sort(vector<int>&nums){
	int len=nums.size();
	for(int i=0;i<len;i++){
		for(int j=0;j<len-i-1;j++){
			if(nums[j]>nums[j+1])swap(nums[j],nums[j+1]);
		}
	}
}