冒泡排序： void bubble_sort(int d[], int size)
{
//假定两两交换发生在数组最后的两个位置
int exchange = size - 1;
while(exchange)
{
//记录下发生数据交换的位置
int bound = exchange;
exchange = 0; //假定本趟比较没有数据交换
for(int i = 0; i < bound; i++)
{
if (d[i] > d[i + 1])
{
//交换
int t = d[i];
d[i] = d[i + 1];
d[i + 1] = t;
exchange = i;
}
}
}
}鸡尾酒排序： function cocktail_sort(list, list_length) // the first element of list has index 0{ bottom = 0; top = list_length - 1; swapped = true; bound = 0; //优化循环次数，记录已经排序的边界，减少循环次数 while(swapped) // if no elements have been swapped, then the list is sorted { swapped = false; for(i = bottom; i < top; i = i + 1) { if(list[i] > list[i+1]) // test whether the two elements are in the correct order { swap(list[i], list[i+1]); // let the two elements change places swapped = true; bound = i; } } // decreases top the because the element with the largest value in the unsorted // part of the list is now on the position top //top = top - 1; top = bound; for(i = top; i > bottom; i = i - 1) { if(list[i] < list[i-1]) { swap(list[i], list[i-1]); swapped = true; bound = i; } } // increases bottom because the element with the smallest value in the unsorted // part of the list is now on the position bottom //bottom = bottom + 1; bottom = bound; }}插入排序： void insert_sort(int *array,unsigned int n) { int i,j; int temp; for(i = 1; i < n; i++) { temp = *(array + i); //已排序部分有i个，接下来将第i+1个元素插入已排序部分 for(j = i;j > 0 && *(array + j - 1) > temp;j--) { *(array + j) = *(array + j - 1); } *(array + j) = temp; } }//归并操作void Merge(int sourceArr[], int targetArr[], int startIndex, int midIndex, int endIndex){ int i, j, k; for(i = midIndex+1, j = startIndex; startIndex <= midIndex && i <= endIndex; j++) { if(sourceArr[startIndex] < sourceArr[i]) { targetArr[j] = sourceArr[startIndex++]; } else { targetArr[j] = sourceArr[i++]; } } if(startIndex <= midIndex) { for(k = 0; k <= midIndex-startIndex; k++) { targetArr[j+k] = sourceArr[startIndex+k]; } } if(i <= endIndex) { for(k = 0; k <= endIndex- i; k++) { targetArr[j+k] = sourceArr[i+k]; } }}//内部使用递归，空间复杂度为n+lognvoid MergeSort(int sourceArr[], int targetArr[], int startIndex, int endIndex){ int midIndex; int tempArr[100]; //此处大小依需求更改 if(startIndex == endIndex) { targetArr[startIndex] = sourceArr[startIndex]; } else { midIndex = (startIndex + endIndex)/2; MergeSort(sourceArr, tempArr, startIndex, midIndex); MergeSort(sourceArr, tempArr, midIndex+1, endIndex); Merge(tempArr, targetArr,startIndex, midIndex, endIndex); }}选择排序： void SelectionSort(int* pDataArray, int iDataNum) { for (int i = 0; i < iDataNum - 1; i++) //从第一个位置开始 { int index = i; for (int j = i + 1; j < iDataNum; j++) //寻找最小的数据索引 if (pDataArray[j] < pDataArray[index]) index = j; if (index != i) //如果最小数位置变化则交换 { int temp=pDataArray [i]； pDataArray [i]=pDataArray[index]； pDataArray[index]=pDataArray[i]； } } } 希尔排序： void ShellSort(int a[], int n){ int d, i, j, temp; for(d = n/2;d >= 1;d = d/2) //一般初次取序列的一半为增量，以后每次减半，直到增量为1 { for(i = d; i < n;i++) //对每组数据（下标相隔d的放在一组）进行直接插入排序 { temp = a[i]; for(j = i - d;(j >= 0) && (a[j] > temp);j = j-d) { a[j + d] = a[j]; } a[j + d] = temp; } }}堆排序： //构建最小堆对数组降序排序 //整理节点 time:O(lg n)template<typename T>void MinHeapify(T* arry,int size,int element) //要求element节点的左右子树已整理好，这样从 //左右子树的根节点选取的较小值一定是最小的{ int lchild=element*2+1,rchild=lchild+1;//左右子树 while(rchild<size)//子树均在范围内 { if(arry[element]<=arry[lchild]&&arry[element]<=arry[rchild])//如果比左右子树都小，完成整理 { return; } if(arry[lchild]<arry[rchild])//如果左边最小 { swap(arry[element],arry[lchild]);//把左面的提到上面 element=lchild;//接下来整理左子树，右子树没变，仍满足最小堆条件 } else//否则右面最小 { swap(arry[element],arry[rchild]);//同理 element=rchild; } lchild=element*2+1; rchild=lchild+1;//重新计算子树位置 } if(lchild<size&&arry[lchild]<arry[element])//只有左子树且左子树小于自己 { swap(arry[lchild],arry[element]); } return;} //堆排序 time:O(n lg n)template<typename T>void HeapSort(T* arry,int size){ int i; for(i=size-1;i>=0;i--)//从子树开始整理树 { MinHeapify(arry,size,i); } while(size>0)//拆除树 { swap(arry[size-1],arry[0]);//将根（最小）与数组最末交换 size--;//树大小减小 MinHeapify(arry,size,0);//整理树 } return;}void quick_sort(int s[ ], int l, int r) //对数组s中下标l到r之间的数进行快速排序 if (l < r) { //Swap(s[l], s[(l + r) / 2]); //如果想以中间数作为关键数据，只需先将中间的这个数和第一个数交换 int i = l, j = r, x = s[l]; while (i < j) { while(i < j && s[j] >= x) // 从右向左找第一个小于x的数 j--; if(i < j) s[i++] = s[j]； while(i < j && s[i] < x) // 从左向右找第一个大于等于x的数 i++; if(i < j) s[j--] = s[i]; } s[i] = x; quick_sort(s, l, i - 1); // 递归调用 quick_sort(s, i + 1, r); } } |
|
|
来自： susongdada > 《CS》
