算法排序

① 几种常用的排序算法比较

排序，从小大，0坐标的在下面，即排序后小的在下面，大的在上面。

1，冒泡Bubble：从第0个开始，一直往上，与相邻的元素比较，如果下面的大，则交换。
Analysis：
Implementation：
void BubbleSort(int *pData, int iNum)

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);
}
}

② 排序算法比较

Private Sub Command1_Click()
Dim a(1 To 100) As Integer
For i = 1 To 100
a(i) = Int(Rnd * 101)
Next
For i = 1 To 100
For j = 1 To i
If a(i) < a(j) Then t = a(i): a(i) = a(j): a(j) = t
Next
Next
For i = 1 To 100
Print a(i);
If i Mod 10 = 0

③ 在各类算法中那种算法排序是最快的

说句实话，没有最快这一说。

1. 如果不在乎浪费空间，应该是桶排序最快

2. 如果整体基本有序，插入排序最快

3. 如果考虑综合情况，快速排序更加实用常见（希尔排序、堆排序等各种排序也各有优劣）

4. 一般情况下，冒泡这种排序仅仅是名字起的有趣罢了，不太好用

④ 简述各种排序算法的优缺点

一、冒泡排序
已知一组无序数据a[1]、a[2]、……a[n]，需将其按升序排列。首先比较a[1]与 a[2]的值，若a[1]大于a[2]则交换 两者的值，否则不变。再比较a[2]与a[3]的值，若a[2]大于a[3]则交换两者的值，否则不变。再比 较a[3]与a[4]，以此 类推，最后比较a[n-1]与a[n]的值。这样处理一轮后，a[n]的值一定是这组数据中最大的。再对a[1]~a[n- 1]以相同方法 处理一轮，则a[n-1]的值一定是a[1]~a[n-1]中最大的。再对a[1]~a[n-2]以相同方法处理一轮，以此类推。共处理 n-1 轮 后a[1]、a[2]、……a[n]就以升序排列了。
优点：稳定；
缺点：慢，每次只能移动相邻两个数据。

二、选择排序
每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数 据元素排完。
选择排序是不稳定的排序方法。
n 个记录的文件的直接选择排序可经过n-1 趟直接选择排序得到有序结果：
①初始状态：无序区为R[1..n]，有序区为空。
②第1 趟排序 在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1 个记录R[1]交换，使R[1..1]和R[2..n]分别变 为记录个数增加1 个的新有序区和记录个数减少1 个的新无序区。
③第i 趟排序
第i 趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R(1≤i≤n-1)。该趟 排序从当前无序区中选出关键字最 小的记录 R[k]，将它与无序区的第1 个记录R 交换，使R[1..i]和R 分别变为记录个数增加1 个的新有序区和记录个数减少 1 个的新无序区。
这样，n 个记录的文件的直接选择排序可经过n-1 趟直接选择排序得到有序结果。
优点：移动数据的次数已知（n-1 次）；
缺点：比较次数多。

三、插入排序
已知一组升序排列数据a[1]、a[2]、……a[n]，一组无序数据b[1]、 b[2]、……b[m]，需将二者合并成一个升序数列。 首先比较b[1]与a[1]的值，若b[1]大于a[1]，则跳过，比较b[1]与a[2]的值， 若b[1]仍然大于a[2]，则继续跳过，直 到b[1]小于a 数组中某一数据a[x]，则将a[x]~a[n]分别向后移动一位，将b[1]插入到原来 a[x]的位置这就完成了b[1] 的插入。b[2]~b[m]用相同方法插入。（若无数组a，可将b[1]当作n=1 的数组a）
优点：稳定，快；
缺点：比较次数不一定，比较次数越少，插入点后的数据移动越多，特别是当数据总量庞大的时候，但用链表可以解决 这个问题。

四、缩小增量排序
由希尔在1959 年提出，又称希尔排序(shell 排序)。
已知一组无序数据a[1]、a[2]、……a[n]，需将其按升序排列。发现当n 不大时，插入 排序的效果很好。首先取一增 量d(d<n)，将a[1]、a[1+d]、a[1+2d]……列为第一组，a[2]、a[2+d]、 a[2+2d]……列为第二组……，a[d]、a[2d]、a[3d]……="" 列为最后一组以次类推，在各组内用插入排序，然后取d'<d，重复上述操="" 作，直到d="1。"
优点：快，数据移动少；=""
缺点：不稳定，d="" 的取值是多少，应取多少个不同的值，都无法确切知道，只能凭经验来取。=""

五、快速排序=""
快速排序是冒泡排序的改进版，是目前已知的最快的排序方法。
="" 已知一组无序数据a[1]、a[2]、……a[n]，需将其按升序排列。首先任取数据a[x]="" 作为基准。比较a[x]与其它数据并="" 排序，使a[x]排在数据的第k="" 位，并且使a[1]~a[k-1]中的每一个数="" 据a[x]，然后采 用分治的策略分别对a[1]~a[k-1]和a[k+1]~a[n] 两组数据进行快速排序。
优点：极快，数据移动少；
缺点：不稳定。

⑤ 快速排序算法

快速排序（Quicksort）是对冒泡排序的一种改进。

然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。

重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

快速排序算法通过多次比较和交换来实现排序，其排序流程如下：

(1)首先设定一个分界值，通过该分界值将数组分成左右两部分。

(2)将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。

⑥ 最好的排序算法是什么算法呀

什么是最好？最快算是最好吗？
目前就所有的内部排序法中，公认的使用广泛的，是快速排序法，平均时间为 kn*lnn ，其中n为待排序序列中记录的个数，k为某个常数。

⑦ 算法排序—冒泡排序

cout<<int_array[i]<<endl;相当于printf("%d /n",int_array[i]);
cout<<endl;就是输出一个换行符。

⑧ 排序算法

可能没理解你的意思…我觉得是四次，情况是恰好五个数是从小到大排列，abcde。只要比较a<b,b<c,c<d,d<e便可以了…