Juinjonn

排序（Sort）

发表于 | 分类于 | | 阅读次数

不同的排序在不同的场景会有更高的效率

BubbleSort（冒泡排序）

定义：在同一个数组中，从数组第一个数开始，相邻两个数进行比较，按照小左大右或者大右小左的顺序，依次循环遍历，进行排序！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void BubbleSort(int *arr,int Length)
{
	int i = 0;
	int j = 1;
	int sys = 0;
	for (i = 0; i < Length-1; i++)
	{
		for (j = 0; j < Length-i-1; j++)
		{
			if (arr[j]>arr[j+1])
			{
				arr[j] = arr[j]^arr[j+1];
				arr[j+1] = arr[j]^arr[j+1];
				arr[j] = arr[j]^arr[j+1];
			}
		}
		sys++;
	}
	return ;
}

改进版冒泡排序

在原有的基础上，我们添加了标记！记录了最后一次交换的位置！
如5，1，4，6，3，2，7，8，9。最后一次交换的位置在2处，并且设定我们每次循环的到2，不对7，8，9
进行比较，节省我们运算的效率！

冒泡排序是对全部已经排好序列排序最快的

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
void BetterBubbleSort(int *arr,int Length)
{
	int i = 0;
	int j = 1;
	int pmark;
	int sys = 0;
	for (; i < Length-1; i++)
	{
		pmark = 0;
		for (j = 0; j < Length-i-1; j++)
		{
			if (arr[j]>arr[j+1])
			{
				arr[j] = arr[j]^arr[j+1];
				arr[j+1] = arr[j]^arr[j+1];
				arr[j] = arr[j]^arr[j+1];
				pmark = j+1;
			}
		}
		i == Length - pmark - 1;
		sys++;
	}
	return ;
}

不带中间变量实现两个相同类型不同值变量间的互换

  1. 加减法

    1
    2
    3
    4
    5
    int a = 5;
    int b = 3;
    a = a+b;
    b = a-b;
    a = a-b;

  2. 异或^

    1
    2
    3
    4
    5
    int a = 5;
    int b = 3;
    a = a^b;
    b = a^b;
    a = a^b;

ps:若对于*a，*b值进行交换，*a，*b不能指向同一块地址空间！

SelectSort选择排序

首先，用第一个数去和所有数进行比较，选出其中最小的数，放在第一位，在用第二个数去和全部数进行比较，最小的放在第二位，依次循环遍历！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void SelectSort(int *Arr,int nLength)
{
	int i = 0;
	int j = 1;
	int min = 0;
	for (i = 0; i < nLength; i++)
	{
		for (j = i; j < nLength-1; j++)
		{
			if (Arr[i] > Arr[j])
			{
				Arr[j] = Arr[j]^Arr[i];
				Arr[i] = Arr[j]^Arr[i];
				Arr[j] = Arr[j]^Arr[i];
			}
		}
	}
}

代码优化：把每次都交换的位置，换成比较完之后，有一个int记下来，不用每次比较完进行交换，而是最后直接用记录的数组下标进行交换！

InsertSort插入排序

把当前数组分成两部分，第一部分有序，第二部分无序，将无序数组依次插入有序数组里去！
例如数组：10，20，3，8，55.用一个temp保存无序数组第一个

适合场景：每个元素距离其最终位置不远时，我们选择插入排序。

  1. 首先把10当成有序数组的最后一位，20当成无序数组的第一位，20和10比较，20比10大不移动。
  2. 之后用无序数组向后移动一位，变成3，3和20比较，比20小，把3放10和20中间，在用3和10比，比10小，放10前面。
  3. 此时有序最后一位仍是20，用8再去和前面几位有序数组进行比较，一次循环遍历！
    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
    void InsertSort(int arr[],int nLength)
    {
    	int j;//有序数组的最后位置
    	int i;//无序数组的第一个
    	int temp;
    	if(arr == NULL || nLength <=0)return;
    	for(i = 1;i<nLength;i++)
    	{
    		j = i-1;
    		temp = arr[i]; //保存无序数组的第一个
    		//进行比较
    		while(temp < arr[j] && j >=0)
    		{
    			//将前一个元素向后移动 
    			arr[j+1] = arr[j];
    			j--;
    		}
    		//将元素放入其对应位置
    		arr[j+1] = temp;
    	}
    }

快排

快排的优点：是比较次数最少的排序！

挖坑填补法

例如数组：7，2，8，4，3，5。我们用temp标记7

  1. 我们将第一数7当标准值，此时相当于7是一个坑（用粗斜体标记），然后我们从后面依次找比标准值7小的数，
    第一个5就比7小，我们将5放到7的坑里。数组变成5，2，8，4，3，7，这是坑变成最后位数！
  2. 然后我们在前面找一个比标准值大的数，第3个数8比标准值大，这是我们将8填到数7的坑里！这是数组变成了：
    5，2，7，4，3，8，我们对已经操作的数，不再进行考虑比较！
  3. 这时我们在从前面开始找一个数比标准值小的数3，填坑。数组变成了：2，3，4，7，8，此时前面和后面的数，
    皆比标准值小和大！
  4. 标准值前面的数我们看做一个区域，标准值后面的数我们看成一个区域。依次递归循环此区域。
    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
    //挖坑填补法 
    int Sort(int arr[],int nLow,int nHigh)
    {
    	int temp ;
    	temp = arr[nLow]; //保存标准值
    	while(nLow < nHigh)
    	{
    		//从后向前找比标准值小的
    		while( nLow < nHigh)
    		{
    			if(arr[nHigh] > temp)
    			{
    				nHigh--;
    			}
    			//小的放前面
    			else
    			{
    				arr[nLow] = arr[nHigh];
    				nLow++;
    				break;
    			}
    		}
    		//从前往后找比标准值大的
    		while(  nLow < nHigh)
    		{
    			if(arr[nLow] < temp)
    			{
    			nLow++;
    			}
    			//大的放后面
    			else
    			{
    				arr[nHigh] = arr[nLow];
    				nHigh--;
    				break;
    			}
    		}
    	}
    	//填坑
    	arr[nLow] = temp;
    	return nLow;
    }
    void QuickSort(int arr[],int nLow,int nHigh)
    {
    	int nIndex;
    	if(arr == NULL )return;
    	if(nLow < nHigh)
    	{
    		//找到标准值位置
    		nIndex = Sort(arr,nLow,nHigh);
    		//根据标准值将当前数组分割成两部分
    		Sort(arr,nLow,nIndex-1);
    		Sort(arr,nIndex+1,nHigh);
    	}
    }

区间（域）分割法

快排的一种，比挖坑填补法快！类似与挖坑填补法，是其优化升级版吧！
例如，数组：7，5，4，3，6

  1. 我们选最后一个数6作为标准值，有两个标记，一个是循环标记I，一个是区域标记s。s= i - 1
    s用红体标记，i用粗斜体标记！s，7，5，4，3，6
  2. 用数6去和第一个数7比较，比标准值大，7,5,4，3，6，则将遍历元素移动到下一处，比标准值6小，
    则将数5和7交换，5，7，4，3，6。
  3. 将遍历指针指下一处，5，7，4，3，6，比标准值小，将4和第二个数交换。5，4，7，3，6
    移动遍历指针，5，4，7，3，6
  4. 比标准值小，将3和第三个数交换。5，4，3，7，6，移动遍历指针。5，4，3，7，6
  5. 这时遍历结束，判断++s与i是否相等，若不等，5，4，3，7，6，数组[s]与数组[i]交换。
  6. 5，4，3，6，7，此时标准值6前小后大，递归遍历！
    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
    //区间分割法
    int Sort(int arr[],int nLow,int nHigh)
    {
    	int nSmall;//小区间的右边界
    	nSmall = nLow-1;
    	for(nLow;nLow < nHigh;nLow++)
    	{
    		//和标准值进行比较
    		if(arr[nLow] < arr[nHigh])
    		{
    			//扩张小区间
    			if(++nSmall != nLow)
    			{
    				arr[nSmall] = arr[nSmall] ^ arr[nLow];
    				arr[nLow] = arr[nSmall] ^ arr[nLow];
    				arr[nSmall] = arr[nSmall] ^ arr[nLow];
    			}
    		}
    	}
    	//标准值放入对应位置
    	if(++nSmall != nHigh)
    	{
    		arr[nSmall] = arr[nHigh] ^ arr[nSmall];
    		arr[nHigh] = arr[nHigh] ^ arr[nSmall];
    		arr[nSmall] = arr[nHigh] ^ arr[nSmall];
    	}
    	return nSmall;
    }
    void QuickSort(int arr[],int nLow,int nHigh)
    {
    	int nIndex;
    	if(arr == NULL )return;
    	if(nLow < nHigh)
    	{
    		//找到标准值位置
    		nIndex = Sort(arr,nLow,nHigh);
    		//根据标准值将当前数组分割成两部分
    		QuickSort(arr,nLow,nIndex-1);
    		QuickSort(arr,nIndex+1,nHigh);
    	}
    }

快排区间分割优化

若我们选择的标准值恰好是最小值或者最大值，这是快排发生交换的次数最多，如果我们在选择下标的时候进行优化，
我们用随机数选择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
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
//找中间值下标
int GetIndex(int arr[],int nLow,int nHigh)
{
	int a,b,c;
	srand(time(NULL));
	//随机出三个在下标范围之内的下标
	a = rand()%(nHigh-nLow+1) + nLow;
	b = rand()%(nHigh-nLow+1) + nLow;
	c = rand()%(nHigh-nLow+1) + nLow;
	//找到三个的中间值
	if(arr[a] > arr[b])
	{
		if(arr[b] > arr[c])
			return b;
		else
		{
			if(arr[a] < arr[c])
				return a;
			else
				return c;
		}		
	}
	else
	{
		if(arr[a] > arr[c])
			return a;
		else
		{
			if(arr[b] < arr[c])
				return b;
			else
				return c;
		}
	}
}
//区间分割法
int Sort(int arr[],int nLow,int nHigh)
{
	int nSmall;//小区间的右边界
	int nIndex;
	nSmall = nLow-1;
	//降低标准值是最大最小值得概率
	nIndex = GetIndex(arr,nLow,nHigh);
	if(nIndex != nHigh)
	{
		arr[nIndex] = arr[nIndex] ^ arr[nHigh];
		arr[nHigh] = arr[nIndex] ^ arr[nHigh];
		arr[nIndex] = arr[nIndex] ^ arr[nHigh];
	}
	for(nLow;nLow < nHigh;nLow++)
	{
		//和标准值进行比较
		if(arr[nLow] < arr[nHigh])
		{
			//扩张小区间
			if(++nSmall != nLow)
			{
				arr[nSmall] = arr[nSmall] ^ arr[nLow];
				arr[nLow] = arr[nSmall] ^ arr[nLow];
				arr[nSmall] = arr[nSmall] ^ arr[nLow];
			}
		}
	}
	//标准值放入对应位置
	if(++nSmall != nHigh)
	{
		arr[nSmall] = arr[nHigh] ^ arr[nSmall];
		arr[nHigh] = arr[nHigh] ^ arr[nSmall];
		arr[nSmall] = arr[nHigh] ^ arr[nSmall];
	}
	return nSmall;
}
void QuickSort(int arr[],int nLow,int nHigh)
{
	int nIndex;
	if(arr == NULL )return;
	if(nLow < nHigh)
	{
		//找到标准值位置
		nIndex = Sort(arr,nLow,nHigh);
		//根据标准值将当前数组分割成两部分
		QuickSort(arr,nLow,nIndex-1);
		QuickSort(arr,nIndex+1,nHigh);
	}
}

快排终极优化

如果数量过少时，直接采用插入排序！

CountSort计数排序

基于非比较排序
适用场景：数据分配非常密集的时候！
例如数组：2，1，3，1，2，2，3，4

  1. 首先在数组中找到最大值和最小值。
  2. 然后申请一个max-min+1的数组空间。
  3. 遍历数组，如第一个数2，就在申请的数组空间下标为2-最小值的位置+1。
    相当于在申请的数组第2个位置，计数加一，每次遇到相同的值都加一。
  4. 相当于在申请的数组空间对应下标对应着参数数组中的值，记录其出现的次数。
  5. 遍历申请的数组空间，对应着下标将值依次存入参数数组。
    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
    void CountSort(int arr[],int nLength)
    {
    	int *pCount = NULL;
    	int i;
    	int j;
    	int nMin,nMax;
    	if(arr == NULL || nLength <=0)return;
    	//找最大值和最小值
    	nMax = arr[0];
    	nMin = arr[0];
    	for(i = 1;i<nLength;i++)
    	{
    		if(arr[i] > nMax)
    		{
    			nMax = arr[i];
    		}
    		if(arr[i] < nMin)
    		{
    			nMin = arr[i];
    		}
    	}
    	//开辟计数数组
    	pCount = (int *)malloc(sizeof(int ) * (nMax-nMin+1));
    	memset(pCount,0,sizeof(int ) * (nMax-nMin+1));
    	//计数
    	for(i = 0;i<nLength;i++)
    	{
    		pCount[arr[i]-nMin]++;
    	}
    	//放回原数组
    	j = 0;
    	for(i = 0;i< nMax-nMin+1;i++)
    	{
    		while(pCount[i] != 0)
    		{
    			arr[j] = i+nMin;
    			j++;
    			pCount[i]--;
    		}
    	}
    }

ShellSort希尔排序

插入排序的优化，按步长进行分组，然后在组内进行插入排序，然后在二分法步长，重复此过程。（ps:不一定要二分步长）

使用场景：数据少的时候！

例如：35，5，9，12，21，8，7，4，13，25，21，14，长度，n

  1. 第一次：$ gap=\displaystyle\frac{n}{2}=6 $，也就是说差6为一组，35和7一组，5和4，9和13，12和25，21和21，8和14。
    每组内进行插入排序，所以35和7互换位置，5和3互换位置。数组：7，4，9，12，21，8，33，5，13，25，21，14
  2. 第二次：$ gap=\displaystyle\frac{gap}{2}=3 $，差3为一组，7，12，33，25一组，4，21，5，21一组，9，8，13，14一组。每组内进行插入排序，25和33换，31和5换。数组：7，4，8，12，5，9，25，21，13，33，21，14
  3. 第三次：$ gap=\displaystyle\frac{gap}{2}=1 $向下取整。所以直接对整个数组进行一次插入排序。
  4. 总结：每次进行组内的插入排序，都是为了让元素距其最终位置更近一步！
    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
    void ShellSort(int arr[],int nLength)
    {
    	int gap;
    	int i; //小组
    	int j;//插入排序
    	int k;
    	int temp;//保存无序数组的第一个
    	if(arr == NULL || nLength <=0)return;
    	//定步长
    	for(gap = nLength/2 ; gap >0 ; gap/=2)
    	{
    		//按照步长分组
    		for(i = 0;i<gap;i++)
    		{
    			//各组内部插入排序
    			for(j = i+gap;j<nLength;j+=gap)
    			{
    				k = j - gap; //有序数组的最后一个
    				temp = arr[j]; //无序数组的第一个
    				while(arr[k] > temp && k >=i)
    				{
    					arr[k +gap] = arr[k];
    					k-=gap;
    				}
    				arr[k+gap] = temp;
    			}
    		}
    	}
    }

希尔排序的优化

分组时，让各组一起进行插入排序，都只进行一次，然后循环进行，代码看起来简洁，但是实际耗时基本相同！

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
void ShellSort2(int arr[],int nLength)
{
	int gap;
	int i; //小组
	int j;//插入排序
	int k;
	int temp;//保存无序数组的第一个
	if(arr == NULL || nLength <=0)return;
	//定步长
	for(gap = nLength/2 ; gap >0 ; gap/=2)
	{
		for(i = gap;i<nLength;i++)
		{
			//各组内部插入排序
				k = i - gap; //有序数组的最后一个
				temp = arr[i]; //无序数组的第一个
				while(arr[k] > temp && k >=0)
				{
					arr[k +gap] = arr[k];
					k-=gap;
				}
				arr[k+gap] = temp;
		}
	}
}

MergeSort归并排序

先拆分再合并。有2路，3路，5路等，这里用2路作为举例说明。先将数组按照二分法（2路）进行递归拆分，
拆分到每个块里只剩一个元素，然后和相邻元素进行比较排序合并，在比较在合并。

流程

Alt text

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
void Merge(int arr[],int nLow,int nHigh)
{
	int nBegin1;
	int nEnd1;
	int nBegin2;
	int nEnd2;
	int *pTemp = NULL;
	int i;
	nBegin1 = nLow;
	nEnd1 = (nLow+nHigh)/2;
	nBegin2 = nEnd1+1;
	nEnd2 = nHigh;
	pTemp = (int *)malloc(sizeof(int ) *(nHigh-nLow+1));
	//合并
	i = 0;
	while(nBegin1 <=nEnd1 && nBegin2 <= nEnd2)
	{
		if(arr[nBegin1] < arr[nBegin2])
		{
			pTemp[i] = arr[nBegin1];
			nBegin1++;
		}
		else
		{
			pTemp[i] = arr[nBegin2];
			nBegin2++;	
		}
		i++;
	}
	//将有剩余的数组元素放入临时数组
	while(nBegin1 <= nEnd1)
	{
		pTemp[i] = arr[nBegin1];
		i++;
		nBegin1++;
	}
	while(nBegin2 <= nEnd2)
	{
		pTemp[i] = arr[nBegin2];
		i++;
		nBegin2++;
	}
	//将临时数组元素放回原数组
	for(i = 0;i < nHigh-nLow +1;i++ )
	{
		arr[i+nLow] = pTemp[i];
	}
	//释放
	free(pTemp);
	pTemp = NULL;
}
void MergeSort(int arr[],int nLow,int nHigh)
{
	int nMid;
	if(arr == NULL )return;
	//两路归并
	nMid = (nLow + nHigh)/2;
	if(nLow < nHigh)
	{
		//先拆分 
		MergeSort(arr,nLow,nMid);
		MergeSort(arr,nMid+1,nHigh);
		//合并
		Merge(arr,nLow,nHigh);
	}
}

HeapSort堆排序

堆排序是顺序储存，分为大根堆（大堆）和小根堆（小堆）。
大堆：父亲结点一定是三个结点最大的！
小堆：父亲结点一定是三个结点最小的！
并且左右儿子结点并没有什么大小顺序关系，我们只是把这个顺序存储的结构看作是二叉树的结构，
我们仅仅是看作二叉树的形式，实际上也是在数组进行操作，并且根据完全二叉树性质(第5条)来进行排序，对此我们要先掌握二叉树的基本知识。

适用场景：在n个元素里找前几个最大的或最小的，我们用堆，并且找大的用小堆，找小的用大堆。

例如：一个数组｛10，2，7，4，6，12，11，9，8｝
Heap1

  1. 首先数组按照二叉树的形势，我们只是按照二叉树对应的性质来将数组假想成二叉树的样子（并没有真正的改变数组的结构）。
  2. 我们按照图2的方式，从下往上从右往左的调整结点的位置，使其遵循大堆的特点！
  3. 图三是我们第一次调整好成大堆的样子。
  4. 图四我们将堆顶和数组最后一个元素对换。
  5. 然后重新按照前面的步骤调整成大堆，最后我们二叉树的第一个结点就是最大的数，依次类推。二叉树链接

堆排序类型题

类型题小结：

  1. 在一个数组中找出前4个最大的数？
    答：首先我们想到的是用小堆，我们建立一个只有四个结点的小堆(图在下面)，将数组元素一次放入小堆，并调整成小堆，这是用数组第五元素和堆顶元素比较，若比堆顶元素大的话，则把堆顶元素放入小堆，并移走小堆的最后一个元素（左边最下面），循环完数组小堆里的数就是前4大的！
  2. 在50亿个数里找出前50大？
    答：还是用小堆，建50个结点，将数据根据内存容量分流，依次按流通过小堆，每个流里选出前50大的，最后在整合到一起，在选出前50的数？
  3. 在一个数据流中找到中位数？数据流：一直不间断提供数据，随时提供，不是一个固定的数组。
    建立一个大堆和小堆，将数据丢入大堆，并且调整大堆，把大堆堆顶扔小堆里，当来数据的时候，调整小堆，把小堆堆顶放大堆里，来数据时，放入大堆并调整大堆，把大堆堆顶放入小堆里。依次循环过程。此时，小堆堆顶是较大数里最小的，大堆堆顶是比较小数里最大的。若数据的个数为奇数时，小堆堆顶是其中位数。当数据的个数为偶数时，小堆堆顶和大堆堆顶的和除2是其中位数。

Heap2

堆排序代码

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
#define nLeft nRootID*2+1
#define nRight nRootID*2+2
void Adjust2(int arr[],int nLength,int nRootID)
{
	int nMax;
	//在有孩子的情况下  假设左孩子是大的    
	for(nMax = nLeft;nLeft < nLength;nMax = nLeft /*下一次继续假设左孩子是最大的8*/)
	{
		//两个孩子
		if(nRight < nLength)
		{
			//右孩子大  
			if(arr[nMax] < arr[nRight])
			{
				nMax = nRight;
			}
		}
		//大的  和父亲比较  大  则交换
		if(arr[nMax] > arr[nRootID])
		{
			arr[nMax] = arr[nRootID] ^ arr[nMax];
			arr[nRootID] = arr[nRootID] ^ arr[nMax];
			arr[nMax] = arr[nRootID] ^ arr[nMax];
			nRootID = nMax;
		}
		else
		{
			break;
		}
	}
}
void HeapSort(int arr[],int nLength)
{
	int i;
	if(arr == NULL || nLength <=0)return;
	//建初始堆
	for(i = nLength/2-1;i>=0;i--)
	{
		Adjust2(arr,nLength,i);
	}
	//排序
	for(i = nLength-1;i>0;i--)
	{
		//最大值放后面
		arr[i] = arr[i] ^ arr[0];
		arr[0] = arr[i] ^ arr[0];
		arr[i] = arr[i] ^ arr[0];
		//调整根节点
		Adjust2(arr,i,0);
	}
}

BucketSort（桶排序）

基于哈希查找，用桶原理进行排序。

哈希查找可以去我的博客,也可以看我的简书查找的算法。推荐去博客，因为可以看latex数学公式。、

桶排序更多时候是用来给小数排序的。

  1. 这里就以整数举例说明，例如数组｛19，27，55，31，47，50，16，21，22，25｝，我们按照每隔十位为一个桶。
  2. 10~20，20~30，30~40，40~50，50~60，共分为5个桶。
  3. 将数字按照其范围放入桶内。
  4. 之后在每个桶内进行排序，排好序之后依次从1桶开始倒回原数组（不给图了，读者可以自行画下，很简单）。这时排序就完成了。
    BucketSort

    由于是链表的头添加，所以数字是到过来的顺序！

桶排序代码

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
typedef struct node
{
	int nValue;
	struct node *pNext;
}MyBucket;
void FindMaxMin(int arr[],int nLength,int *nMin,int* nMax)
{
	int i;
	*nMin = arr[0];
	*nMax = arr[0];
	for(i = 1;i<nLength;i++)
	{
		if(arr[i] < *nMin)
		{
			*nMin = arr[i];
		}
		if(arr[i] > *nMax)
		{
			*nMax = arr[i];
		}
	}
}
void BucketSort(int arr[],int nLength)
{
	int nMax;
	int nMin;
	int i;
	MyBucket **pBucket = NULL;
	int nMinIndex;
	int nMaxIndex;
	int nIndex;
	MyBucket *pTemp = NULL;
	MyBucket *pMark = NULL;
	int temp;
	if(arr == NULL || nLength <=0)return;
	//找到最大值 最小值
	FindMaxMin(arr,nLength,&nMin,&nMax);
	nMinIndex = nMin/10;
	nMaxIndex = nMax/10;
	//桶的确定
	pBucket = (MyBucket **)malloc(sizeof(MyBucket*) *(nMaxIndex-nMinIndex+1));
	memset(pBucket,0,sizeof(MyBucket*) *(nMaxIndex-nMinIndex+1));
	//各元素入桶
	for(i = 0;i<nLength;i++)
	{
		nIndex = arr[i]/10 - nMinIndex;
		pTemp = (MyBucket*)malloc(sizeof(MyBucket) );
		pTemp->nValue = arr[i];
		pTemp->pNext = pBucket[nIndex];
		pBucket[nIndex] = pTemp;
	}
	//各桶内排序
	for(i = 0;i<nMaxIndex-nMinIndex +1;i++)
	{
		//冒泡排序
		pMark = pBucket[i];
		
		while(pMark )
		{
			pTemp = pBucket[i];
			while(pTemp->pNext )
			{
				if(pTemp->nValue > pTemp->pNext->nValue)
				{
					temp = pTemp->nValue;
					pTemp->nValue = pTemp->pNext->nValue;
					pTemp->pNext->nValue = temp;
				}
				pTemp = pTemp->pNext;
			}
			pMark = pMark->pNext;
		}
	}
	//倒回原数组
	i = 0;
	for(temp = 0;temp <nMaxIndex-nMinIndex +1;temp++ )
	{
		//遍历各个桶
		pMark = pBucket[temp];
		while(pMark)
		{
			arr[i] = pMark->nValue;
			i++;
			pMark = pMark->pNext;
		}
	}
	//释放空间
	for(temp = 0;temp <nMaxIndex-nMinIndex +1;temp++)
	{
		//释放每个桶
		pMark = pBucket[temp];
		while(pMark)
		{
			pTemp = pMark;
			pMark = pMark->pNext;
			free(pTemp);
			pTemp = NULL;
		}
	}
	free(pBucket);
	pBucket = NULL;
}

RadinSort(LSD)基数排序

基数排序分两种一种是LSD，一种是MSD，这个就说LSD,因为MSD类似LSD而且使用的不是很频繁，如想了解，看完LSD会事半功倍。LSD也是基于桶原理，而且是从位数开始排序的。

哈希查找可以去我的博客,也可以看我的简书查找的算法。推荐去博客，因为可以看latex数学公式。

例如数组：｛124，11，25，3，221，215，306，35，23，14，10，1，111｝
从低位开始算起，也就是个位开始的。因为十进制最后也就是0~9十个数字，所以我们要十个桶。

  1. 按照数组的顺序，依次入桶，所以我们这时应该是链表的尾添加
    个位：
    RadinSort-1
  2. 将桶内元素倒回数组，顺序不可以变，也就是10，11，221，1，111，3，23，124，14，25，215，35，306.这个顺序进入链表。
  3. 按照十位的数字进行分桶，从数组依次入桶。
    十位：
    RadinSort-2
  4. 再将桶内元素倒入数组，同样顺序不可以变，也就是1，3，306，10，11，111，14，215，221，23，124，25，35.这个顺序。
  5. 按照百位，依次入桶。
    百位：
    RadinSort-3
  6. 在倒入数组中，此时我们的排序就完成了。

代码

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
typedef struct node
{
	int nValue;
	struct node *pNext;
}MyRadix;
int FindMax(int arr[],int nLength)
{
	int i;
	int nMax = arr[0];
	for(i = 1;i<nLength;i++)
	{
		if(arr[i] > nMax)
		{
			nMax = arr[i];
		}
	}
	return nMax;
}
int GetLoopTimes(int nMax)
{
	int i = 0;
	while(nMax)
	{
		nMax/=10;
		i++;
	}
	return i;
}
void Sort(int arr[],int nLength,int i)
{
	int nBase = 1;
	MyRadix **pRadix = NULL;
	int j;
	int k;
	MyRadix *pTemp = NULL;
	int nIndex;
	MyRadix *pMark = NULL;
	//申请桶
	pRadix = (MyRadix **)malloc(sizeof(MyRadix*) * 10);
	memset(pRadix,0,sizeof(MyRadix*) * 10);
	//求被除基数
	while(i > 1)
	{
		nBase *= 10;
		i--;
	}
	//数字入桶
	for(j = 0;j <nLength; j++)
	{
		nIndex = arr[j]/nBase%10;
		pTemp = (MyRadix*)malloc(sizeof(MyRadix));
		pTemp->nValue = arr[j];
		pTemp->pNext = NULL;
		//尾添加
		if(pRadix[nIndex] == NULL)
		{
			pRadix[nIndex] = pTemp;
		}
		else
		{
			pMark = pRadix[nIndex];
			while(pMark->pNext)
			{
				pMark = pMark->pNext;
			}
			pMark->pNext = pTemp;
		}
	}
	//放回原数组
	j = 0;
	for(k = 0;k<10;k++)
	{
		pMark = pRadix[k];
		while(pMark)
		{
			arr[j] = pMark->nValue;
			j++;
			pMark = pMark->pNext;
		}
	}
	//空间释放
	for(k = 0;k<10;k++)
	{
		pMark = pRadix[k];
		while(pMark)
		{
			pTemp = pMark;
			pMark = pMark->pNext;
			free(pTemp);
			pTemp = NULL;
		}
	}
	free(pRadix);
	pRadix = NULL;
}
void RadixSort(int arr[],int nLength)
{
	int i;
	int nMax;
	int nLoopTimes;
	if(arr == NULL || nLength <=0)return;
	//找最大值
	nMax = FindMax(arr,nLength);
	//获得循环次数
	nLoopTimes = GetLoopTimes(nMax);
	//数组元素按照各位依次入桶
	for(i = 1;i<=nLoopTimes;i++)
	{
		//个 十 百 位处理
		Sort(arr,nLength,i);
	}
}
技术无价，一元美滋滋！