C はコンピューター プログラミングで広く使用されているプログラミング言語であり、ソート アルゴリズムはプログラミングでよく使用されるアルゴリズムの 1 つです。並べ替えアルゴリズムをマスターすると、効率的なプログラムを作成する能力が向上し、プログラミング スキルが向上します。この記事では、C で一般的に使用される並べ替えアルゴリズムを紹介します。
バブル ソートは、シーケンス内の隣接する要素を比較することによって、大きな要素をシーケンスに入れ替える基本的な並べ替えアルゴリズムです。具体的には、バブル ソートは各ラウンドで隣接する要素のサイズを比較し、最後の要素がソートされるまで大きい要素を後方に入れ替えます。
C コードは次のとおりです。
void bubbleSort(int arr[], int n)
{
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j+1]) {
// 交换元素
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}選択ソートは、ソートのたびに未ソートの部分を選択する単純なソート アルゴリズムです。最小の要素をソートされたセクションの最後に配置します。具体的には、選択ソートは各ラウンドで最小の要素を選択し、それを現在の位置の要素と交換します。
C コードは次のとおりです。
void selectionSort(int arr[], int n)
{
int minIndex, temp;
for (int i = 0; i < n - 1; i++) {
minIndex = i; // 记录最小元素的位置
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
// 更新最小元素的位置
minIndex = j;
}
}
// 交换元素
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}挿入ソートは、要素を既に挿入されている要素に挿入する、シンプルで直感的な並べ替えアルゴリズムです。ソートされたシーケンスが長くなり、ソートされたシーケンスが長くなります。具体的には、挿入ソートの各ラウンドでは、ソートされた部分配列に要素を挿入し、残りの要素を後方に移動します。
C コードは次のとおりです。
void insertionSort(int arr[], int n)
{
int key, j;
for (int i = 1; i < n; i++) {
key = arr[i]; // 待插入的元素
j = i - 1;
// 将大于待插入元素的元素向后移动
while (j >= 0 && arr[j] > key) {
arr[j+1] = arr[j];
j--;
}
// 将待插入元素插入到正确的位置
arr[j+1] = key;
}
}クイック ソートは、シーケンスをソートするためにピボット要素を選択する効率的なソート アルゴリズムです。 1 つはピボット要素よりも小さく、もう 1 つはピボット要素よりも大きい 2 つの部分に分割し、2 つの部分シーケンスを再帰的に並べ替えます。具体的には、クイック ソートは各ラウンドでピボット要素を選択し、ピボット要素より小さい要素をピボット要素の左側に配置し、ピボット要素より大きい要素を右側に配置します。次に、左と右のサブシーケンスが同じ方法で再帰的に並べ替えられます。
C コードは次のとおりです。
void quickSort(int arr[], int left, int right)
{
int i = left, j = right;
int pivot = arr[(left + right) / 2]; // 选择枢纽元素
while (i <= j) {
// 找到左侧大于枢纽元素的元素
while (arr[i] < pivot) {
i++;
}
// 找到右侧小于枢纽元素的元素
while (arr[j] > pivot) {
j--;
}
// 交换左右元素
if (i <= j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
// 递归排序左侧和右侧的子序列
if (left < j) {
quickSort(arr, left, j);
}
if (i < right) {
quickSort(arr, i, right);
}
}マージ ソートは、シーケンスを分割する古典的な分割統治ソート アルゴリズムです。 2 つのサブシーケンスに分割し、各サブシーケンスを個別に並べ替えて、最後に 2 つの順序付けられたサブシーケンスをマージします。具体的には、マージ ソートはまずシーケンスを 2 つのサブシーケンスに分割し、その 2 つのサブシーケンスを再帰的に並べ替えてから、2 つの順序付けされたサブシーケンスを 1 つの順序付けされたシーケンスにマージします。
C コードは次のとおりです:
void merge(int arr[], int left, int mid, int right)
{
int i, j, k;
int n1 = mid - left + 1;
int n2 = right - mid;
int L[n1], R[n2];
// 将数据拷贝到两个临时数组中
for (i = 0; i < n1; i++)
L[i] = arr[left + i];
for (j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
i = 0; // 左侧子数组的索引
j = 0; // 右侧子数组的索引
k = left; // 合并后的数组的索引
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// 将左侧子数组的剩余元素拷贝到合并后的数组中
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// 将右侧子数组的剩余元素拷贝到合并后的数组中
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(int arr[], int left, int right)
{
if (left < right) {
int mid = left + (right - left) / 2;
// 递归排序左侧和右侧的子序列
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
// 合并两个有序子数组
merge(arr, left, mid, right);
}
}上記は、C で一般的に使用される 5 つの並べ替えアルゴリズムです。アルゴリズムは退屈に思えますが、プログラミングの重要な部分であり、並べ替えアルゴリズムを学ぶことで、プログラミングの効率と品質を向上させることができます。
以上がC++ で一般的な並べ替えアルゴリズムをマスターするの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。
![[Web フロントエンド] Node.js クイック スタート](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
