轉載請注明出處，如果有筆誤請聯系我 qq 409746848，后續還會基礎出教程，您的關注是我最大的動力，
冒泡
void MaoPao(int * arr , int size)
{
if(!arr || size <= 0) return;
//冒泡演算法核心，從頭到尾進行排序，每輪找出最小的和第一個進行交換
//時間復雜度是O(N平方)
for(int i=0;i<size ; i++)
{
//第二輪從第二個開始
for(int j=i+1;j<size;j++)
{
if(arr[i] > arr [j])
{
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
}
}
}
快排
void qsort(int * arr , int l , int h)
{
//如果低位>=高位表示結束
if(l>=h) return;
int i = l,j=h;
int key = arr[i];//關鍵位置用的是i就要先將i的值填充
while(i<j)
{
//右邊找比key小的放左邊
while(i<j && arr[j]>=key)
{
j--;
}
arr[i] = arr[j];
//左邊找比key大的放右邊
while(i<j && arr[i]<=key){
i++;
}
arr[j] = arr[i];
}
//關鍵值放入中間位置
arr[i] = key;
qsort(arr , l , i - 1);
qsort(arr, i +1 , h);
}
//-------------------------------------------------------------------------------
//選擇排序
//-------------------------------------------------------------------------------
//選擇排序
void selectSort(int* arr , int size)
{
//每一次都找出剩下佇列中最小的并放置在當前的位置
for (int i=0;i<size;i++)
{
int minpos = i;
for (int j=i+1;j<size;j++)
{
if (arr[j] < arr[minpos])
{
minpos = j;
}
}
int tem = arr[i];
arr[i] = arr[minpos];
arr[minpos] = tem;
}
}
//堆排序
void adjustMaxHeap(int a[], int len, int parentNodeIndex) {
// 若只有一個元素，那么只能是堆頂元素，也沒有必要再排序了
if (len <= 1) {
return;
}
// 記錄比父節點大的左孩子或者右孩子的索引
int targetIndex = -1;
// 獲取左、右孩子的索引
int leftChildIndex = 2 * parentNodeIndex + 1;
int rightChildIndex = 2 * parentNodeIndex + 2;
// 沒有左孩子
if (leftChildIndex >= len) {
return;
}
// 有左孩子，但是沒有右孩子
if (rightChildIndex >= len) {
targetIndex = leftChildIndex;
}
// 有左孩子和右孩子
else {
// 取左、右孩子兩者中最大的一個
targetIndex = a[leftChildIndex] > a[rightChildIndex] ? leftChildIndex : rightChildIndex;
}
// 只有孩子比父節點的值還要大，才需要交換
if (a[targetIndex] > a[parentNodeIndex]) {
int temp = a[targetIndex];
a[targetIndex] = a[parentNodeIndex];
a[parentNodeIndex] = temp;
// 交換完成后，有可能會導致a[targetIndex]結點所形成的子樹不滿足堆的條件，
// 若不滿足堆的條件，則調整之使之也成為堆
adjustMaxHeap(a, len, targetIndex);
}
}
void heapSort(int a[], int len) {
if (len <= 1) {
return;
}
// 初始堆成無序最大堆
// 從完全二叉樹最后一個非子節點開始
// 在陣列中第一個元素的索引是0
// 第n個元素的左孩子為2n+1，右孩子為2n+2，
// 最后一個非子節點位置在(n - 1) / 2
for (int i = (len - 1) / 2; i >= 0; --i) {
adjustMaxHeap(a, len, i);
}
for (int i = len - 1; i > 0; --i) {
// 將當前堆頂元素與最后一個元素交換，保證這一趟所查找到的堆頂元素與最后一個元素交換
// 注意：這里所說的最后不是a[len - 1]，而是每一趟的范圍中最后一個元素
// 為什么要加上>0判斷？每次不是說堆頂一定是最大值嗎？沒錯，每一趟調整后，堆頂是最大值的
// 但是，由于len的范圍不斷地縮小，導致某些特殊的序列出現例外
// 比如說，5, 3, 8, 6, 4序列，當調整i=1時，已經調整為3,4,5,6,8序列，已經有序了
// 但是導致了a[i]與a[0]交換，由于變成了4,3,5,6,8反而變成無序了!
if (a[0] > a[i]) {
int temp = a[0];
a[0] = a[i];
a[i] = temp;
}
// 范圍變成為：
// 0...len-1
// 0...len-1-1
// 0...1 // 結束
// 其中，0是堆頂，每次都是找出在指定的范圍內比堆頂還大的元素，然后與堆頂元素交換
adjustMaxHeap(a, i - 1, 0);
}
}
//-------------------------------------------------------------------------------
//插入排序
//-------------------------------------------------------------------------------
//普通插入排序
void InsertSort(int* arr , int size)
{
//從第一個元素開始，認為第一個元素是已經排序好的佇列
//從后面元素中找到比前一個小的位置
//從這個位置向前遍歷找到比這個位置小的位置插入，否則這個值就往后移動一個位置
for (int i = 1 ; i<size ; i++)
{
int prepos = i-1;
int curval = arr[i];
while(prepos >=0 && arr[prepos] > curval )
{
arr[prepos+1] = arr[prepos];
prepos-- ;
}
arr[prepos+1] = curval;
}
}
//折半插入排序(也叫希爾排序)
void HalfInsertSort(int* arr , int size)
{
//一半一半的執行插入排除
for (int i = size/2 ; i>0 ; i = i/2)
{
for (int j = i ; j<size ; j++)
{
int pos = j;
int curval = arr[j];
while(pos-i >= 0 && arr[pos-i] > curval)
{
//后移
arr[pos] = arr[pos-i];
pos = pos - i;
}
arr[pos] = curval;
}
}
}
//-------------------------------------------------------------------------------
//歸并排序
//-------------------------------------------------------------------------------
//二路歸并 和 多路歸并
//對每一路進行歸并排序
void MergeSort(int* arr , int* temp , int startindex,int endindex)
{
int mid = 0;
if (startindex < endindex)
{
mid = startindex+(endindex - startindex)/2;
MergeSort(arr,temp,startindex , mid);
MergeSort(arr,temp,mid+1 , endindex);
//合并兩個陣列
int i=startindex,k=startindex,j=mid+1;
//兩部分對比，取更小的部分繼續往后移動
while(i<mid+1 && j < endindex+1)
{
if (arr[i] > arr[j])
{
temp[k++] = arr[j++];
}
else
{
temp[k++] = arr[i++];
}
}
//復制左邊剩下的
while(i < mid+1)
{
temp[k++] = arr[i++];
}
//復制右邊剩下的
while(j<endindex+1)
{
temp[k++] = arr[j++];
}
//陣列還原
for (i = startindex ; i<endindex+1 ; i++)
{
arr[i] = temp[i];
}
}
}//-------------------------------------------------------------------------------
//非比較排序
//-------------------------------------------------------------------------------
//-------------------------------------------------------------------------------
//計數排序,比較的元素差值不要太大
//-------------------------------------------------------------------------------
void CountSort(int* arr , int size)
{
int max = arr[0],min = arr[0];
//找出最大和最小
for (int i=0;i<size;i++)
{
if (arr[i] > max) max = arr[i];
if (arr[i] < min) min = arr[i];
}
int newlen = max - min + 1;
int* newIntArr = new int[newlen];
memset(newIntArr , 0 , newlen*sizeof(int));
//開始計數
for (int i=0;i<size;i++)
{
newIntArr[ arr[i] - min ] += 1;
}
//開始取出有序填入原陣列
for (int i=0,j=0;i<newlen ; i++)
{
while(newIntArr[i]--)
{
arr[j++] = i+min;
}
}
delete [] newIntArr;
}
//-------------------------------------------------------------------------------
//桶排序 是計數排序的升級版,需要知道:1.幾個桶;2.每個桶有幾個元素
//-------------------------------------------------------------------------------
typedef struct bucket{
int k;
bucket* next;
}bucket;void bucketSort(int* arr , int size , int bucket_elm_size)
{
int min = arr[0] , max = arr[0];
for (int i=0;i<size;i++)
{
if(arr[i] > max) max = arr[i];
if(arr[i] < min) min = arr[i];
}
int bucket_count = (max - min) / bucket_elm_size + 1;
//初始化桶子
bucket* pbuckets = new bucket[bucket_count];
for(int i = 0 ;i<bucket_count ; i++)
{
pbuckets[i].k = 0;
pbuckets[i].next = 0;
}
//將資料入桶
for(int i = 0 ;i<size ; i++)
{
int index = (arr[i]-min)/bucket_elm_size;
bucket* pFindBucket = &pbuckets[index];
//使用插入排序
bucket* pNewBucket = new bucket;
pNewBucket->k = arr[i];
pNewBucket->next = NULL;
if (pFindBucket->k == 0)
{
pFindBucket->k += 1;
pFindBucket->next = pNewBucket;
}
else
{
while(pFindBucket->next != NULL && pFindBucket->next->k <= pNewBucket->k )
pFindBucket = pFindBucket->next;
pNewBucket->next = pFindBucket->next;
pFindBucket->next = pNewBucket;
pbuckets[index].k += 1;
}
}
//輸出資料
for (int i=0,j=0;i<bucket_count;i++)
{
for(bucket* pBucket = pbuckets[i].next;pBucket!=NULL;)
{
bucket* tmp = pBucket;
arr[j++] = pBucket->k;
pBucket = pBucket->next;
delete tmp;
}
}
delete [] pbuckets;
}
//基數排序
//需要找到最大數，計算基數，然后存盤基數
void RadixSort(int* arr , int size)
{
unsigned int max = 0;
for (int i=0;i<size;i++)
{
if (abs(arr[i]) > max)
{
max = abs(arr[i]);
}
}
int bucketCount = 10;
int radix = 1;//最大有多少個數量級
while(max / (int)pow((float)10,radix))
{
radix++;
}
bucket * pRadixArr = new bucket[10];
for (int i=0;i<bucketCount;i++)
{
pRadixArr[i].k = 0;
pRadixArr[i].next = NULL;
}
int mod = 10;//求余模數
int dev = 1;//除數
for (int i=0;i<radix;i++,dev *= 10 , mod *= 10)
{
for (int j = 0 ; j< size ; j++)
{
bucket* pNewBucket = new bucket;
pNewBucket->k = arr[j];
pNewBucket->next = NULL;
//求出個位或者10位對應的桶序號
int radixIndex = arr[j] % mod / dev;
bucket* pFind = &pRadixArr[radixIndex];
if (pFind->k == 0)
{
pFind->k += 1;
pFind->next = pNewBucket;
}
else
{
while(pFind->next != NULL && pFind->next->k <= pNewBucket->k) pFind = pFind->next;
pNewBucket->next = pFind->next;
pFind->next = pNewBucket;
pRadixArr[radixIndex].k += 1;
}
}
//從小到大取出桶的資料即可
int pos = 0;
for (int j = 0 ; j<bucketCount ; j++)
{
if (pRadixArr[j].k)
{
bucket* pNode = pRadixArr[j].next;
while(pNode)
{
bucket* pNodeDel = pNode;
arr[pos++] = pNode->k;
pNode = pNode->next;
delete pNodeDel;
}
pRadixArr[j].k = 0;
pRadixArr[j].next = NULL;
}
}
}
delete[] pRadixArr;
}
//十種排序演算法
int _tmain(int argc, _TCHAR* argv[])
{
int aa[]={6,5,8,9,1,10,65,85,95,111,254,3,22,16,28};
int bb[ARRSIZE(aa)];
RadixSort(aa,ARRSIZE(aa));
bucketSort(aa,ARRSIZE(aa),5);
CountSort(aa , ARRSIZE(aa));
heapSort(aa , ARRSIZE(aa));
MergeSort(aa ,bb, 0,ARRSIZE(aa)-1);
HalfInsertSort(aa , ARRSIZE(aa));
InsertSort(aa,ARRSIZE(aa));
selectSort(aa,ARRSIZE(aa));
MaoPao(aa,ARRSIZE(aa));
qsort(aa,0,ARRSIZE(aa)-1);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/263011.html
標籤：其他