快速排序最坏的情况
这个答案还得看枢轴（pivot）的选择策略。在快速排序的早期版本中呢，最左面或者是最右面的那个元素被选为枢轴，那最坏的情况就会在下面的情况下发生啦：
1）数组已经是正序（same order）排过序的。
2）数组已经是倒序排过序的。
3）所有的元素都相同（1、2的特殊情况）
因为这些案例在用例中十分常见，所以这个问题可以通过要么选择一个随机的枢轴，或者选择一个分区中间的下标作为枢轴，或者（特别是对于相比更长的分区）选择分区的第一个、中间、最后一个元素的中值作为枢轴。有了这些修改，那快排的最差的情况就不那么容易出现了，但是如果输入的数组最大（或者最小元素）被选为枢轴，那最坏的情况就又来了。
冒泡排序
一.冒泡排序简介(从小到大排序）
-
比较相邻的元素。如果第一个比第二个大，就交换他们两个。
-
比较相邻的元素。如果第一个比第二个大，就交换他们两个。
-
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
-
针对所有的元素重复以上的步骤，除了最后一个，即需要进行length-1次。
-
第一次是对n个数进行n-1次比较，进行到最后第n个的一个是最大的；
-
第二次是对n-1个数进行n-2次比较，进行到最后第n-1个的一个是最大的；
-
……
-
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
动态图：
二.代码案例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
package day0515;
public class demo_sort {
public static void main(String[] args) {
//冒泡排序算法
int[] numbers=new int[]{1,5,8,2,3,9,4};
//需进行length-1次冒泡
for(int i=0;i<numbers.length-1;i++)
{
for(int j=0;j<numbers.length-1-i;j++)
{
if(numbers[j]>numbers[j+1])
{
int temp=numbers[j];
numbers[j]=numbers[j+1];
numbers[j+1]=temp;
}
}
}
System.out.println("从小到大排序后的结果是:");
for(int i=0;i<numbers.length;i++)
System.out.print(numbers[i]+" ");
}
}
|
有内存限制的海量数据排序
磁盘文件排序
问题描述：
输入：给定一个文件，里面最多含有n个不重复的正整数（也就是说可能含有少于n个不重复正整数），且其中每个数都小于等于n，n = 10^7。
输出：得到按从小到大升序排列的包含所有输入的整数的列表。
条件：最多有大约1MB的内存空间可用，但磁盘空间足够。且要求运行时间在五分钟以下，10秒为最佳结果。
分析： 首先注意的是它的内存要求，基本上否决了大多数的排序算法。 文件里面的数据是不重复的，这个很关键，因为下面的方案前提就是数据不重复。
1、位图方案
用数组或者字符串代表位图。下标代表数字，值代表这个数字出现的次数。
以位为最小单位，对应位为1，代表位数值，可以用20位长的字符串来表示一个所有元素都小于20的简单的非负数集合，边框用如下字符串来表示集合{1,2,3,5,8,13}：
01110100100001000000
对应位置则置1，没用对应数的位置则置0，开始扳手指头数数吧。我们可以采用一个具有1000万个位的字符串来表示这个文件，其中，当整数i在文件中时，第i位为1。
第一步，所有位置0,将集合初始化。
第二步，通过读入文件中的每个整数来建立集合，将对应的位都置1.
第三步，检验每一位，如果该位为1，就输出对应的整数。
这里不得不提一下c++库中的一个容器bitset,发现这个在处理位的时候简直牛，先来瞅瞅。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
#include <iostream>
#include <bitset>
using namespace std;
int main()
{
const int max = 20;
int arr[10] = {2,9,3,5,4,0,18,11,12,15};
bitset<max> bit_map; //一种类模板，放入长度，定义了一个max位，每位都为0
bit_map.reset(); //所有位置0
int i;
for(i = 0;i< 10;i++)
{
bit_map.set(arr[i]); //将对应位置1
}
for(i = 0;i< max;i++)
{
if(bit_map.test(i)) //判断第i位，如果为1，返回true
cout << i << " ";
}
cout << endl;
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
|
#include <iostream>
#include <bitset>
#include <assert.h>
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
const int MAX = 5000000;
int main()
{
clock_t begin = clock();
bitset<MAX> bit_map;
bit_map.reset();
FILE * fp_unsort_file = fopen("data.txt","r");
assert(fp_unsort_file);
int num;
while(fscanf(fp_unsort_file,"%d ",&num)!= EOF)
{
if(num < MAX) //先对1-4999999的数进行排序
bit_map.set(num);
}
FILE * fp_sort_file = fopen("sort.txt","w");
assert(fp_sort_file);
int i;
for(i= 0;i < MAX;i++)
{
if(bit_map.test(i))
fprintf(fp_sort_file,"%d ",i);
}
int result = fseek(fp_sort_file,0,SEEK_SET); //指针回到文件开始处
if(result)
cout << "fseek failed" << endl;
else
{
bit_map.reset();
while(fscanf(fp_unsort_file,"%d ",&num) !=EOF)
{
if(num > MAX && num < 10000000) //再对5000000-10000000的数排序
{
num -=MAX;
bit_map.set(num);
}
}
for(i = 0;i<MAX;i++)
{
if(bit_map.test(i))
fprintf(fp_sort_file,"%d ",i+MAX);
}
}
clock_t end = clock();
cout << "time is:" << endl;
cout << (end-begin)/CLOCKS_PER_SEC << "s" << endl;
fclose(fp_sort_file);
fclose(fp_unsort_file);
return 0;
}
|
第一次只处理1-4999999之间的数据，对这些数进行位图排序，只需要约5000000/8 = 625000byte，就是0.625M,排序后输出。
第二次,扫描输入文件，只处理4999999-10000000的数据项，只需要0.625M,因此只需要0.625M。
2、多路归并
我们先了解一下，归并排序的过程，归并排序就是2路归并。
归并排序的过程：
（1）把无序表的每一个元素看做是一个有序表，则有n个有序子表；
（2）把n个有序表按相邻位置分成若干对，每对中的两个表进行归并，归并后子表数减少一半。
（3）反复进行这一过程，直到归并为一个有序表为止。
是采用分治法的典型应用
首先考虑下如何将二个有序数列合并，比较二个数列第一个数，谁小就放入到临时数组中，然后再进行比较，如果一个数列到达结尾，直接将另一个数列放入就临时数组中。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
void MemeryArray(int a[],int n,int b[],int m,int c[])
{
int i,j,k;
i = j= k = 0;
while(i < n && j< m)
{
if(a[i] < b[j])
c[k++] = a[i++];
else
c[k++] = b[j++];
}
while(i < n)
c[k++] = a[i++];
while(j < n)
c[k++] = b[j++];
}
|
下一步考虑如何让两个A,B数组有序，可以将A,B各自再分成二组，依次类推，当分出来的小组只有一个元素时，这个小组内已经达到有序了，然后再合并相邻的二个小组就可以了，先递归分解，再合并数列就完成了归并排序。
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
|
//将二个有序数列a[first...mid] 和a[mid+1...last]合并
void MemeryArray(int a[],int first,int mid,int last,int temp[])
{
int i = first;
int j = mid+1;
int m = mid;
int n = last;
int k = 0;
while(i <= m && j< =n)
{
if(a[i] < b[j])
temp[k++] = a[i++];
else
temp[k++] = a[j++];
}
while(i <= m)
temp[k++] = a[i++];
while(j <=n)
temp[k++] = a[j++];
for(i = 0;i<k;i++)
a[first+i] = temp[i];
}
void mergesort(int a[],int first,int last,int temp[])
{
if(first < last)
{
int mid = (first + last)/2;
mergesort(a,first,mid,tmep);
mergesort(a,mid+1,last,temp);
MemeryArray(a,first,mid ,last,temp);
}
}
|
归并排序是一种稳定排序，时间复杂度最好情况下和最坏情况下均是O（nlogn）
多路归并就是从多个有序数列中归并。
比如将10000000的数据，分成40个有序文件，分别在内存中排序，然后对这40个有序文件进行归并排序。
（1）读取每个文件中第一个数（每个文件的最小数），存放在一个大小为40的data数组中，
（2）选择data数组中最小的数min_data，及其相应的文件索引（来自哪个文件）index
（3）将min_data写入到文件result，然后更新数组data(根据index,读取该文件的下一个数代替min_data）
（4）判读是否所有数据都读取完毕，否则返回到2步。
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
|
#include <iostream>
#include <string>
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
int sort_num = 10000000;
int memory_size = 250000; //每次排序250000个数据
int read_data(FILE *fp,int *space)
{
int index = 0;
while(index < memory && fscanf(fp,"%d ",&space[index])!= EOF)
index++;
return index;
}
void write_data(FILE * fp,int *space,int num)
{
int index = 0;
while(index < num)
{
fprintf(fp,"%d ",space[index]);
index++;
}
}
void check_fp(FILE *fp)
{
if(fp == NULL)
{
cout << "the file not open" << endl;
exit(1);
}
}
int compare(const void * a,const void * b)
{
return *(int *)a-*(int *)b;
}
string new_filename(int n)
{
char file_name[20];
sprintf(file_name,"data%d.txt",n);
return file_name;
}
//将原文件分割成多个小文件，并在内存中排序
int memroy_sort()
{
FILE * fp_in_file = fopen("data.txt","r");
check_fp(fp_in_file);
int counter = 0;
while(true)
{
int * space = new int(memory_size);
int num = read_data(fp_in_file,space);
if(num == 0)
break;
qsort(space,num,sizeof(int),compare);
string file_name = new_filename(++counter);
FILE *fp_aux_file = fopen(file_name,"w");
check_fp(fp_aux_file);
write_data(fp_aux_file,space,num);
fclose(fp_aux_file);
delete []space;
}
fclose(fp_in_file);
return counter;
}
//将n个小文件归并为一个文件，多路归并
void merge_sort(int file_num)
{
if(file_num < 0)
return;
FILE *fp_out_file = fopen("result.txt","w");
check_fp(fp_out_file);
FILE ** fp_array = new FILE*[file_num]; //存放每个小文件的指针的数组
int i;
for(i = 0;i<file_num;i++)
{
string file_name = new_file_name(i+1);
fp_array[i] = fopen(file_name,"r");
check_fp(fp_array[i]);
}
int * first_data = new int [file_num];
bool * finish = new bool[file_num]; //文件是否读取到结尾
memset(finish,false,sizeof(bool) * file_num);
for(i = 0;i<file_num;i++)
fscanf(fp_array[i],"%d ",&first_data[i]);
while(true)
{
int index = 0;
while(index < file_num && finish(index))
index++;
if(index >=file_name)
break;
int min_data = first_data[index];
for(i = index+1;i<file_name,i++)
{
if(min_data > first_data[i] && !finish[index])
{
min_data = first_data[i];
index = i;
}
}
fprintf(fp_out_file ,"%d ",min_data); //将最小的输出
if(fscanf(fp_array[index],"%d ",&first_data[index]) == EOF) //根据index，找到该文件的下一个数，放入到first_data中。如果这个文件已经读取到结尾，则将标志置为true。
finish(index) = true;
}
fclose(fp_out_file);
delete []finish;
delete[]first_data;
for(i = 0;i<file_num;i++)
fclose(fp_array[i]);
delete[] fp_array;
}
int main()
{
clock_t start = clock();
int aux_file_num = memory_sort();
clock_t memory_end = clock();
cout << "time need in memory sort" << memory_end-start << endl;
merge_sort(aux_file_num);
clock_t end = clock();
cout << "the time need in merge sort" << end - memory_end << endl;
return 0;
}
|
qsort()用法
int cmp(const void* a,const void * b);
void qsort(char *,int n,int m,cmp);
包含在stdlib.h中，函数四个参数，
参与排序的数组，元素个数，单个元素到小(sizeof),比较函数。
再说比较函数，返回正数，a要放在b后面，返回负数，a要放在b前面，返回0，相等。
解决问题的关键是在于熟悉一个算法，而不是某一问题，
3、通过这个问题，我们学到了两种方法：
一种：位图法。 针对与不重复数据排序，进行数据的快速查找，判重，删除。
二中：多路归并。 海量数据，内存有限的情况下。
