c++排序

最新推荐文章于 2022-04-14 22:00:00 发布

EvenHong

最新推荐文章于 2022-04-14 22:00:00 发布

阅读量170

点赞数

分类专栏： c++ 文章标签： html5 html css

本文链接：https://blog.csdn.net/EvenHong/article/details/120144467

版权

c++ 专栏收录该内容

22 篇文章

订阅专栏

本文介绍了C++实现的四种排序算法：冒泡排序、选择排序、堆排序和归并排序。通过具体代码展示了每种排序算法的原理和步骤，帮助读者理解排序算法的实现细节。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

1.冒泡排序：

int A[] = { 1,2,3,4,5,7,8,9,90,543,345,678,890,123,432,543,654,765,867 };
void swap(int& a,int& b) {
   int tmp;
   tmp = a;
   a = b;
   b = tmp;
}

void printArray(int *array,int length) {
   for (int i = 0; i < length; i++) {
       cout << array[i] << endl;
   }
}

void sortpaopao(int a[],int length) {
   int loop;
   for (loop = 0; loop < length - 1; loop++) {
       for (int i = 0; i < length - loop - 1; i++) {
           if (a[i]>a[i+1]) {
               int tmp = a[i];
               a[i] = a[i+1];
               a[i + 1] = tmp;
           }
       }
   }
}

2.选择排序（不稳定）

void selectionSort(int a[], int length) {
   for (int loop = 1; loop < length; loop++) {
       for (int j = 0; j < length - loop; j++) {
           if (a[j] > a[length-loop]) {//把每一次循环中最大的那个放在最后面
               swap(a[j], a[length - loop]);
           }
       }
   }
}

3.推排序（不稳定）

void heapify(int b[],int loopSize,int i) {
   int top = i;
   int lson = 2 * i + 1;
   int rson = 2 * i + 2;
   if (lson < loopSize && b[top] < b[lson]) {
       top = lson;
   }
   if(rson < loopSize&& b[top] < b[rson]) {
       top = rson;
   }
   if (top != i) {
       swap(b[top], b[i]);
       heapify(b, loopSize, top);
   }
}
void heapSort(int a[], int length) {
   int i;
   for (i = length / 2 - 1; i >= 0; i--)
       heapify(a, length, i);
   for (int i = length - 1; i > 0; i--) {
       swap(a[i], a[0]);
       heapify(a, i, 0);
   }
   for (int j = 0; j < length; j++) {
       cout << a[j] << endl;
   }
}

//4.插入排序（稳定）

void insertSort(int a[], int length) {
   for (int loop = 1; loop < length; loop++) {
       int tmp = a[loop];
       for (int i = loop-1; i >=0; i--) {
           if (tmp < a[i]) {
               a[i + 1] = a[i];
           }
           else {
               a[i + 1] = tmp;
               break;
           }
       }
   }
   for (int j = 0; j < length; j++) {
       cout << a[j] << endl;
   }
}

5.归并排序

void merge(int a[], int low,int mid,int height) {
   int s1 = low;//第一段的开始
   int s2 = mid + 1;//第二段的开始
   vector<int> ret;
   ret.resize(height - low + 1);
   /*int* ret = new int[height - low + 1];*/
   int i = 0;//表示ret数组下标
   while (s1 <= mid && s2 <= height) {//两个归并段都有数据
       if (a[s1] <= a[s2]) {
           ret[i++] = a[s1++];
       }
       else {
           ret[i++] = a[s2++];
       }
   }
   while (s1 <= mid) {
       ret[i++] = a[s1++];
   }
   while (s2 <= height) {
       ret[i++] = a[s2++];
   }
   for (int j = 0; j < ret.size(); j++) {
       a[j + low] = ret[j];
   }
}
void mergeSort(int a[], int low, int height) {
   if (low >= height) {
       return;
   }
   int mid = (low + height)/2;
   mergeSort(a, low, mid);
   mergeSort(a, mid + 1, height);
   merge(a,low,mid,height);
}

int main() {
   int length = sizeof(A) / sizeof(int);
// sortpaopao(A, length);

//selectionSort(A, length);
   for (int i = 0; i < length; i++) {
       cout << A[i] << endl;
   }
   return 0;
}