几种常用的排序算法? 八种? 十种?
/Files/toMyself/最常用的排序算法总结.doc参考:
http://en.wikipedia.org/wiki/Sorting_algorithm 排序,从小大,0坐标的在下面,即排序后小的在下面,大的在上面。
1,冒泡Bubble:从第0个开始,一直往上,与相邻的元素比较,如果下面的大,则交换。
Analysis:
Implementation:
void BubbleSort(int *pData, int iNum)
{
int i, j;
int temp;
for (i = iNum - 1; i > 0; i--)
{
for(j = 0; j < i; j++)
{
if(pData[j] > pData[j+1])
{
temp = pData[j];
pData[j] = pData[j+1];
pData[j+1] = temp;
}
}
}
} 2,插入Insertion:与打扑克牌时整理牌很想象,假定第一张牌是有序的,从第二张牌开始,拿出这张牌来,往下比较,如果有比这张牌大的,则把它拨到上一个位置,直到找到比手上的这张更小的(或到顶了),
则把手上的这张牌插入到这张更小的牌的后面。
Analysis:
Implementation:
void InsertionSort(int *list, int length)
{
int i, j, temp;
for (i = 1; i < length; i++)
{
temp = list[i];
j = i - 1;
while ((j >= 0) && (list[j] > temp))
{
list[j+1] = list[j];
j--;
}
list[j+1] = temp;
}
} 3,选择Selection:从所有元素中找到最小的放在0号位置,从其它元素(除了0号元素)中再找到最小的,放到1号位置,......。
Analysis:
Implementation:
void SelectionSort(int data[], int count)
{
int i, j, min, temp;
for (i = 0; i < count - 1; i++)
{
/**//* find the minimum */
min = i;
for (j = i+1; j < count; j++)
{
if (data[j] < data[min])
{
min = j;
}
}
/**//* swap data[i] and data[min] */
temp = data[i];
data[i] = data[min];
data[min] = temp;
}
} 4,快速Quick:先拿出中间的元素来(值保存到temp里),设置两个索引(index or pointer),一个从0号位置开始往最大位置寻找比temp大的元素;一个从最大号位置开始往最小位置寻找比temp小的元素,找到了或到顶了,则将两个索引所指向的元素
互换,如此一直寻找交换下去,直到两个索引交叉了位置,这个时候,从0号位置到第二个索引的所有元素就都比temp小,从第一个索引到最大位置的所有元素就都比temp大,这样就把所有元素分为了两块,然后采用前面的办法分别排序这两个部分。总的来
说,就是随机找一个元素(通常是中间的元素),然后把小的放在它的左边,大的放右边,对左右两边的数据继续采用同样的办法。只是为了节省空间,上面采用了左右交换的方法来达到目的。
Analysis:
Implementation:
void QuickSort(int *pData, int left, int right)
{
int i, j;
int middle, iTemp;
i = left;
j = right;
middle = pData[(left + right) / 2]; //求中间值
do
{
while ((pData[i] < middle) && (i < right)) //从左扫描大于中值的数
i++;
while ((pData[j] > middle) && (j > left)) //从右扫描小于中值的数
j--;
if (i <= j) //找到了一对值
{
//交换
iTemp = pData[i];
pData[i] = pData[j];
pData[j] = iTemp;
i++;
j--;
}
} while (i <= j); //如果两边扫描的下标交错,就停止(完成一次)
//当左边部分有值(left<j),递归左半边
if(left < j)
QuickSort(pData, left, j);
//当右边部分有值(right>i),递归右半边
if(right > i)
QuickSort(pData, i, right);
} 5,希尔Shell:是对Insertion Sort的一种改进,在Insertion Sort中,从第2个位置开始取出数据,每次都是与前一个(step/gap==1)进行比较。Shell Sort修改为,在开始时采用较大的步长step,
从第step位置开始取数据,每次都与它的前step个位置上的数据进行比较(如果有8个数据,初始step==4,那么pos(4)与pos(0)比较,pos(0)与pos(-4),pos(5)与pos(1),pos(1)与pos(-3),
...... pos(7)与pos(3),pos(3)与pos(-1)),然后逐渐地减小step,直到step==1。step==1时,排序过程与Insertion Sort一样,但因为有前面的排序,这次排序将减少比较和交换的次数。
Shell Sort的时间复杂度与步长step的选择有很大的关系。Shell排序比冒泡排序快5倍,比插入排序大致快2倍。Shell排序比起QuickSort,MergeSort,HeapSort慢很多。但是它相对比较简单,它适合
于数据量在5000以下并且速度并不是特别重要的场合。它对于数据量较小的数列重复排序是非常好的。
Analysis:
Implementation:
template<typename RandomIter, typename Compare>
void ShellSort(RandomIter begin, RandomIter end, Compare cmp)
{
typedef typename std::iterator_traits<RandomIter>::value_type value_type;
typedef typename std::iterator_traits<RandomIter>::difference_type diff_t;
diff_t size = std::distance(begin, end);
diff_t step = size / 2;
while (step >= 1)
{
for (diff_t i = step; i < size; ++i)
{
value_type key = *(begin+i);
diff_t ins = i; // current position
while (ins >= step && cmp(key, *(begin+ins-step)))
{
*(begin+ins) = *(begin+ins-step);
ins -= step;
}
*(begin+ins) = key;
}
if(step == 2)
step = 1;
else
step = static_cast<diff_t>(step / 2.2);
}
}
template<typename RandomIter>
void ShellSort(RandomIter begin, RandomIter end)
{
typedef typename std::iterator_traits<RandomIter>::value_type value_type;
ShellSort(begin, end, std::less<value_type>());
} 6,归并Merge:先将所有数据分割成单个的元素,这个时候单个元素都是有序的,然后前后相邻的两个两两有序地合并,合并后的这两个数据再与后面的两个合并后的数据再次合并,充分前面的过程直到所有的数据都合并到一块。
通常在合并的时候需要分配新的内存。
Analysis:
Implementation:
void Merge(int array[], int low, int mid, int high)
{
int k;
int *temp = (int *) malloc((high-low+1) * sizeof(int)); //申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
int begin1 = low;
int end1 = mid;
int begin2 = mid + 1;
int end2 = high;
for (k = 0; begin1 <= end1 && begin2 <= end2; ++k) //比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
{
if(array[begin1]<=array[begin2])
{
temp[k] = array[begin1++];
}
else
{
temp[k] = array[begin2++];
}
}
if(begin1 <= end1) //若第一个序列有剩余,直接拷贝出来粘到合并序列尾
{
memcpy(temp+k, array+begin1, (end1-begin1+1)*sizeof(int));
}
if(begin2 <= end2) //若第二个序列有剩余,直接拷贝出来粘到合并序列尾
{
memcpy(temp+k, array+begin2, (end2-begin2+1)*sizeof(int));
}
memcpy(array+low, temp, (high-low+1)*sizeof(int));//将排序好的序列拷贝回数组中
free(temp);
}
void MergeSort(int array[], unsigned int first, unsigned int last)
{
int mid = 0;
if (first < last)
{
mid = (first+last)/2;
MergeSort(array, first, mid);
MergeSort(array, mid+1,last);
Merge(array,first,mid,last);
}
} 7,堆Heap:一棵堆积树(堆)满足条件:子结点的键值或索引总是小于(或者大于)它的父节点。
堆排序适合于数据量非常大的场合(百万数据)。
堆排序不需要大量的递归或者多维的暂存数组。这对于数据量非常巨大的序列是合适的。比如超过数百万条记录,因为快速排序,归并排序都使用递归来设计算法,在数据量非常大的时候,可能会发生堆栈溢出错误。
堆排序会将所有的数据建成一个堆,最大的数据在堆顶,然后将堆顶数据和序列的最后一个数据交换。接下来再次重建堆,交换数据,依次下去,就可以排序所有的数据。
特点
堆排序(HeapSort)是一树形选择排序。堆排序的特点是:在排序过程中,将R[l..n]看成是一棵完全二叉树的顺序存储结构,利用完全二叉树中双亲结点和孩子结点之间的内在关系(参见二叉树的顺序存储结构),在当前无序区中选择关键字最大(或最小)的记录
堆排序与直接选择排序的区别
直接选择排序中,为了从R[1..n]中选出关键字最小的记录,必须进行n-1次比较,然后在R[2..n]中选出关键字最小的记录,又需要做n-2次比较。事实上,后面的n-2次比较中,有许多比较可能在前面的n-1次比较中已经做过,但由于前一趟排序时未保留这些比较结果,所以后一趟排序时又重复执行了这些比较操作。
堆排序可通过树形结构保存部分比较结果,可减少比较次数。
算法分析
堆[排序的时间,主要由建立初始]堆和反复重建堆这两部分的时间开销构成,它们均是通过调用Heapify实现的。
堆排序的最坏时间复杂度为O(nlogn)。堆序的平均性能较接近于最坏性能。
由于建初始堆所需的比较次数较多,所以堆排序不适宜于记录数较少的文件。
堆排序是就地排序,辅助空间为O(1),
它是不稳定的排序方法。
实际上,堆的构建和更新都可以使用非递归的方式实现,对于堆的构建,需要首先找到最后一个有孩子的节点array[k],然后从array[k]一直更新到array[0]即可,其中的k=n/2。k的求法如下:假设k存在
,2*k+1=n或者2*k+2=n,对于第一种情况,k==n/2,对于第二种情况,k==n/2-1。对于堆的更新,就更简单了,只要从array[0]开始,选择一条通路,一直向下更新,直到没有孩子了为止。
值得注意的是,对于下标从0开始的数组,k号节点的孩子节点分别是2*k+1和2*k+2。而对于下标从1开始得数组,k号节点的孩子节点分别是2*k和2*k+1。
堆排序属于选择排序,实际上就是利用最大堆这个数据结构,每次选择一个剩余元素中最大的元素,交换到合适的位置上去。
/**//*單一子結點最大堆積樹調整*/
void Max_Heapify(int A[], int i, int heap_size)
{
int l = 2 * i; // 左子結點
int r = 2 * i + 1; // 右子結點
int largest;
int temp;
if(l < heap_size && A[l] > A[i])
{
largest = l;
}
else
{
largest = i;
}
if(r < heap_size && A[r] > A[largest])
{
largest = r;
}
if(largest != i)
{
temp = A[i];
A[i] = A[largest];
A[largest] = temp;
Max_Heapify(A, largest, heap_size);
}
}
/**//*建立最大堆積樹*/
void Build_Max_Heap(int A[], int heap_size)
{
for(int i = heap_size; i >= 0; i--)
{
Max_Heapify(A, i, heap_size);
}
}
/**//*堆積排序程序碼*/
void HeapSort(int A[], int heap_size)
{
int temp;
Build_Max_Heap(A, heap_size);
for(int i = heap_size - 1; i >= 1; i--)
{
temp = A[0];
A[0] = A[i];
A[i] = temp;
heap_size = heap_size - 1;
Max_Heapify(A, 0, heap_size);
}
}
8,基数Radix:采用的是一种数据位的比较,比如比较整数的个位、十位等,比较字符串的第一个字符、第二个字符等。
参考:
http://en.wikipedia.org/wiki/Radix_sort9,计数Counting:
10,桶/箱Bucket:
测试:
1,测试数据只有1个、2个、3个、4个、5个。
2,测试数据很大,有奇数个、有偶数个。
3,测试数据中有多个是相等的值。
注:
附件中上传了一个我从往上找来的,别人对常用排序算法的总结,看看别人的描述,再看看自己的,很多地方都说得不大清楚,什么时候能够达到人家那样的水平,排序算法差不多也能过了吧!
扩展:
1,貌似所有的排序都以可随机访问的数组(array or vector or string)为例,其它存储方式(链表list)的数据的排序怎么办呢?
2,排序举例的时候大都以整形数的排序为例,如果是其它数据结构的排序怎么办了? 有没有更通用的排序算法实现?比较、交换两种操作单独写成函数指针或函数对象,可行吗?
3,几种算法更加C++化的实现?