各种排序算法的实现、总结

1. 排序算法

比较排序

非比较排序

计数排序、基数排序

2. 排序算法的实现

假定序列array[10]={73,22,93,43,55,14,28,65,39,81} (以升序为例)

直接插入排序

直接插入排序就是每一步都将一个待排数据按其大小插入到已经排序的数据中的适当位置，直到全部插入完毕。

 1 void Insertsort(int* array,size_t n)
 2 {
 3     assert(array);
 4     for (size_t i = 0; i < n-1; i++)
 5     {
 6         int end = i;
 7         int temp = array[end+1];
 8         while (end >= 0 && array[end]>temp)
 9         {
10             array[end + 1] = array[end];
11             --end;
12         }
13         array[end + 1] = temp;
14     }
15 }

希尔排序

希尔排序（ShellSort）又称为“缩小增量排序”。该方法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接

插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。

 1 void Shellsort(int* array, size_t n)
 2 {
 3     assert(array);
 4     int gap = n;
 5     while (gap > 1)
 6     {
 7         gap = gap / 3 + 1;
 8         for (size_t i = 0; i < n - gap; i++)
 9         {
10             int end = i;
11             int temp = array[end + gap];
12             while (end>=0 && array[end] > temp)
13             {
14                 array[end + gap] = array[end];
15                 end -= gap;
16             }
17             array[end + gap] = temp;
18         }
19     }
20 }

选择排序

选择排序(Selectsort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

 1     void Selectsort( int *array, int n)  
 2     {  
 3          int i, j, min, temp;  
 4         for( i = 0; i < n - 1; i ++)  
 5         {  
 6             min = i;  
 7             //查找最小值  
 8             for( j = i + 1; j < n; j ++)  
 9                 if( array[ min] > array[ j])  
10                {
11                     min = j; 
12              }
13             if( min != i)  
14             {  
15                 temp = array[ min];  
16                 array[ min] = array[ i];  
17                 array[ i] = temp;  
18             }  
19         }  
20     }

简单选择排序算法改进

传统的简单选择排序,每趟循环只能确定一个元素排序后的定位。我们可以考虑改进为每趟循环确定两个元素(当前趟最大和最小记录)的位置,从而减少排序所需的循环次数。

改进后对n个数据进行排序,最多只需进行[n/2]趟循环即可。

 1 void Selectsort_op(int *array, int size)
 2 {
 3     assert(array);
 4     int left = 0, right = size - 1;
 5     while (left < right)
 6     {
 7         int minindex = left;
 8         int maxindex = right;
 9         for (int i = left; i <= right; i++)
10         {
11             if (array[i] <= array[minindex])
12             {
13                 minindex = i;
14             }
15             if (array[i]>array[maxindex])
16             {
17                 maxindex = i;
18             }
19         }
20             swap(array[minindex], array[left]);
21             if (maxindex == left)
22             {
23                 maxindex = minindex;
24             }
25             swap(array[maxindex], array[right]); 
26           ++left;
27           --right;
28     }
29 }

堆排序

我们的堆排序算法就是抓住了堆的这一特点，每次都取堆顶的元素，将其放在序列最后面，然后将剩余的元素重新调整为最大堆，依次类推，最终得到排序的序列。

 1 void _Adjustdown(int* array, int root, size_t size)
 2 {
 3     assert(array);
 4     int child = root * 2 + 1;
 5     while (child < size)
 6     {
 7         if (child + 1 < size&&array[child + 1] > array[child])
 8         {
 9             child++;
10         }
11         if (array[child]>array[root])
12         {
13             swap(array[child], array[root]);
14             root = child;
15             child = root * 2 + 1;
16         }
17         else
18             break;
19     }
20 }
21 void Heapsort(int* array,size_t size )
22 {
23     assert(array);
24     //建堆(大堆)
25     for (int i = (size - 2)/2; i >= 0; i--)
26     {
27         _Adjustdown(array, i, size);
28     }
29     //数据调整
30     while (--size)
31     {
32         swap(array[0], array[size]);
33         _Adjustdown(array,0, size);
34     }
35 }

冒泡排序

冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。

走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。(设置一个标志位，判断一次循环便利后是否有发生变换的)

 1 void Bubblesort(int * array, size_t size)
 2 {
 3     assert(array);
 4     int flag = 0;
 5     for (size_t end = size - 1; end >= 0; end--)
 6     {      flag = 0;
 7         for (size_t ibegin = 0; ibegin < end; ibegin++)
 8         {   
 9             if (array[ibegin + 1] < array[ibegin])
10             {
11                 swap(array[ibegin + 1], array[ibegin]);
12                 flag = 1;
13             }
14          }
15         if (flag == 0)
16         {
17             break;
18         }
19     }
20 }

快速排序

选择数列尾元素，称为 "基准"（key），重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。

在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归三种实现方式、两种优化。

优化1：三平取中法

它使得最坏情况发生的几率减小了。

优化2：根据分区大小调整算法

减少递归栈使用的优化，快速排序的实现需要消耗递归栈的空间，而大多数情况下都会通过使用系统递归栈来完成递归求解。

当数据集较小时，不必继续递归调用快速排序算法，使用插入排序代替快速排序。

  1 int Partsort1(int *array, int left, int right)
  2 {
  3     int key = array[right];
  4     int begin = left;
  5     int end = right - 1;
  6     while (begin <end)
  7     {
  8         //找大
  9         while (begin < end&&array[begin] <= key)
 10         {
 11             ++begin;
 12         }
 13         //找小
 14         while (begin<end&&array[end]>key)
 15         {
 16             --end;
 17         }
 18         if (begin <end)
 19         {
 20             swap(array[begin], array[end]);
 21         }
 22         if (array[begin]>array[right])
 23         {
 24             swap(array[begin], array[right]);
 25             return begin;
 26         }
 27     }
 28     return right;
 29 }
 30 //快速排序
 31 int Partsort2(int *array, int left, int right)
 32 {
 33     assert(array);
 34     int key = array[right];
 35     int begin = left;
 36     int end = right;
 37     while (begin < end)
 38     {
 39         while (begin < end&&array[begin] <= key)
 40         {
 41             ++begin;
 42         }
 43         if (begin < end)
 44         {
 45             array[end] = array[begin];
 46         }
 47         while (begin < end&&array[end] >= key)
 48         {
 49             --end;
 50         }
 51         if (begin < end)
 52         {
 53             array[begin] = array[end];
 54         }
 55     }
 56     array[begin] = key;
 57     return begin;
 58 
 59 }
 60 //三数取中法
 61 int FindMidPoint(int left,int mid,int right)
 62 {
 63     if (left <= mid&&left <= right)
 64     {
 65         if (mid <= right)
 66             return mid;
 67         else
 68             return right;
 69     }
 70     else if (mid <= left&&mid <= right)
 71     {
 72         if (left >= right)
 73             return right;
 74         else
 75             return left;
 76     }
 77     else
 78     {
 79         if (left <= mid)
 80             return left;
 81         else
 82             return mid;
 83     }
 84 }
 85 //快速排序
 86 int Partsort3(int *array, int left, int right)
 87 {
 88     assert(array);
 89     int mid = (right - left) / 2 + left;
 90     int ret=FindMidPoint(left, mid, right);
 91     swap(array[ret], array[right]);
 92     int key = array[right];
 93     int prev = left - 1;
 94     int cur = left;
 95     while (cur < right)
 96     {
 97         if (array[cur] < key&& ++prev != cur)
 98         {
 99             swap(array[cur], array[prev]);
100         }
101         ++cur;
102     }
103     swap(array[++prev], array[right]);
104     return prev;
105 }
106 
107 void Quicksort(int *array, int left,int right)
108 {
109     assert(array);
110     if (left >= right)
111     {
112         return;
113     }
114     if (right - left < 16)
115     {
116         Insertsort(array + left, right - left + 1);
117         
118     }
119     int div = Partsort3(array, left, right);
120     Quicksort(array, left, div - 1);
121     Quicksort(array, div + 1, right);
122 
123 }

非递归实现

 1 #include<stack>
 2 void Quicksort_NonR(int *array, int left, int right)
 3 {
 4     assert(array);
 5     stack<int> s;
 6     s.push(right);
 7     s.push(left);
 8     while (!s.empty())
 9     {
10         int begin = s.top();
11         s.pop();
12         int end = s.top();
13         s.pop();
14         int div = Partsort3(array, begin, end);
15         if (begin < div - 1)
16         {
17             s.push(div - 1);
18             s.push(begin);
19         }
20         if (div + 1 < end)
21         {
22             s.push(end);
23             s.push(div + 1);
24         }
25     }
26     
27 }

归并排序

归并排序（Mergesort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。

把长度为n的输入序列分成两个长度为n/2的子序列。

对这两个子序列分别采用归并排序。

将两个排序好的子序列合并成一个最终的排序序列。

在描述归并排序的步骤时又调用了归并排序本身，可见这是一个递归的过程。

 1 void _Merge(int* array, int *tmp, int begin1, int end1,int begin2,int end2)
 2 {
 3     int index = begin1;
 4     while (begin1 <= end1&&begin2 <= end2)
 5     {
 6         if (array[begin1] < array[begin2])
 7         {
 8             tmp[index++] = array[begin1++];
 9         }
10         else
11         {
12             tmp[index++] = array[begin2++];
13         }
14     }
15     while (begin1 <= end1)
16     {
17         tmp[index++] = array[begin1++];
18     }
19     while (begin2 <= end2)
20     {
21         tmp[index++] = array[begin2++];
22     }
23 }
24 void _Mergesort(int *array, int *tmp, int left, int right)
25 {
26     if (left < right)
27     {
28         int mid = left + (right - left) / 2;
29         _Mergesort(array, tmp, left, mid);
30         _Mergesort(array, tmp, mid+1, right);
31         _Merge(array, tmp, left,mid, mid + 1, right);
32         memcpy(array + left, tmp + left, sizeof(int)*(right - left + 1));
33     }
34 }
35 void Mergesort(int *array, size_t n)
36 {
37     assert(array);
38     int *tmp = new int[n];
39     _Mergesort(array, tmp, 0, n - 1);
40     delete[] tmp;
41 }

计数排序

计数排序算法的步骤：

　　找出待排序的数组中最大和最小的元素

　　统计数组中每个值为i的元素出现的次数存入数组Count的第i项

　　反向填充目标数组：将每个元素i放在新数组的第Count(i)项，每放一个元素就将Count(i)减去1

 1 void Countsort(int *array, size_t n)
 2 {
 3     assert(array);
 4     int min = array[0], max = array[0];
 5     for (size_t i = 1; i < n; i++)
 6     {
 7         if (array[i] <= min)
 8             min = array[i];
 9         if (array[i] >= max)
10             max = array[i];
11     }
12     int *Count = new int[max - min + 1];
13     memset(Count, 0, sizeof(int)*(max - min +1));
14     for (int i = 0; i < n; i++)
15     {
16         Count[array[i] - min]++;
17     }
18     size_t index = 0;
19     for (size_t i = 0; i < max - min + 1; i++)
20     {
21         while (Count[i]--)
22         {
23             array[index++] = i + min;
24         }
25     }
26 }

基数排序

 1 int  GetMaxDigit(int *array, size_t n)
 2 {
 3     int base = 10;
 4     int digit = 1;
 5     for (size_t i = 10; i < n; i++)
 6     {
 7         while (array[i] >= base)
 8         {
 9             ++digit;
10             base *= 10;
11         }
12     }
13     return digit;
14 }
15 void LSDsort(int *array, size_t n)
16 {
17     assert(array);
18     int count[10] = {0};
19     int start[10] = {0};
20     int *bucket = new int[10];
21     memset(bucket, 0, sizeof(int)*n);
22     int maxDigit = GetMaxDigit(array, n);
23     int digit = 1;
24     int base = 1;
25     while (digit <= maxDigit)
26     {
27         memset(count, 0, sizeof(int)* 10);
28         //统计位为0~9数据段
29         for (size_t i = 0; i < n; i++)
30         {
31             int num = (array[i] / base) % 10;
32             count[num]++;
33         }
34         //计算在桶里的起始位置
35         start[0] = 0;
36         for (int i = 1; i < 10; i++)
37         {
38             start[i] = start[i - 1] + count[i - 1];
39         }
40         for (size_t i = 0; i < n; i++)
41         {
42             int num = (array[i] / base) % 10;
43             bucket[start[num]++] = array[i];
44         }
45         memcpy(array, bucket, sizeof(int)*n);
46         base *= 10;
47         ++digit;
48         delete[] bucket;
49    }
50 }

3. 排序算法的总结